題意:
? ? ? 求s到t的最短路,如果路徑相同求那么要求另一個權(quán)值盡可能的小.
思路:

? ? ? 水題,就是spfa的比較那個地方多了一個可以更新的機會,當(s_x[xin] > s_x[tou] + E[k].cost || s_x[xin] == s_x[tou] + E[k].cost && s_t[xin] > s_t[tou] + 1) 時更新就行了..

#include<stdio.h> #include<string.h> #include<queue> #include<math.h>#define N_node 100 + 5 #define N_edge 20000 + 500 #define INF 1000000000 using namespace std;typedef struct {int to ,next;double cost; }STAR;typedef struct {double x ,y; }NODE;STAR E[N_edge]; NODE node[N_node]; int list[N_node] ,tot; double s_x[N_node]; int s_t[N_node];void add(int a ,int b ,double c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }double abss(double x) {return x > 0 ? x : -x; } double minn(double x ,double y) {return x < y ? x : y; }void SPFA(int s ,int n) {for(int i = 0 ;i <= n ;i ++)s_x[i] = INF ,s_t[i] = INF;int mark[N_node] = {0};mark[s] = 1;s_x[s] = s_t[s] = 0;queue<int>q;q.push(s);while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost || abss(s_x[xin] - s_x[tou] + E[k].cost) < 1e-6 && s_t[xin] > s_t[tou] + 1){s_x[xin] = s_x[tou] + E[k].cost;s_t[xin] = s_t[tou] + 1;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}}return ; }int main () {int n ,i ,j;double d;while(~scanf("%d %lf" ,&n ,&d)){for(i = 1 ;i <= n ;i ++)scanf("%lf %lf" ,&node[i].x ,&node[i].y);memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= n ;i ++)for(j = i + 1 ;j <= n ;j ++){double dis = pow(node[i].x - node[j].x ,2.0) + pow(node[i].y - node[j].y,2.0);if(dis <= d * d) {add(i ,j ,sqrt(dis));add(j ,i ,sqrt(dis));}}int s = 0 ,t = n + 1;for(i = 1 ;i <= n ;i ++){double dis = pow(node[i].x,2.0) + pow(node[i].y ,2.0);if(pow(d + 7.5 ,2.0) >= dis)add(s ,i ,sqrt(dis) - 7.5);dis = minn(50 - abss(node[i].x) ,50 - abss(node[i].y));if(dis <= d) add(i ,t ,dis);}if(d >= 50 - 7.5)add(s ,t ,50 - 7.5);SPFA(s ,t);if(s_x[t] == INF)printf("can't be saved\n");elseprintf("%.2lf %d\n" ,s_x[t] ,s_t[t]);}return 0; }

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu1245 两个权值的最短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。