给定一个无向带权网络，无负边，无重边和自环，每个顶点有一个正数权值。首先求特定原点s到终点d的最短路的个数；然后求所有最短路中顶点权值a[i]之和最大的那条，输出这条路径。
可用dijkstra算法求出所有最短路，用一个pathNum[u]数组记录从s到u的最短路的个数，查找链path[u]保存了到u为止使顶点权值a[i]之和最大的那条路径，sum[u]保存了这条路径的顶点权值和。
对于提交后的第3个测试点，注意更新新引入顶点u的邻居v的距离值dis[v]时，sum[v]无条件更新为sum[u]+a[v]，因为要先满足最短路这个条件，得到的顶点才有意义。最短路更新，则sum要重新计算。
参考了博客 http://blog.csdn.net/tc_to_top/article/details/51427223
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define RINT(V) scanf("%d", &(V)) 9 #define FREAD() freopen("in.txt", "r", stdin) 10 #define REP(N) for(int i=0; i<(N); i++) 11 #define REPE(N) for(int i=1; i<=(N); i++) 12 #define PINT(N) printf("%d", (N)) 13 #define PSTR(S) printf("%s", S) 14 #define RSTR(S) scanf("%s", S) 15 #define pn() printf("\n") 16 #define pb(V) push_back(V) 17 #define CLEAR(A, V) memset((A), (V), sizeof(A)) 18 using namespace std; 19 typedef long long ll; 20 const int MAX_N = 505; 21 const int INF = 0x3fffffff; 22 23 int n, m, s, d; 24 int a[MAX_N]; 25 26 int V; 27 int G[MAX_N][MAX_N];//邻接矩阵，无边是INF, 自己到自己是0 28 int dis[MAX_N];//单源最短路数组 29 int vis[MAX_N]; 30 int path[MAX_N], pathNum[MAX_N]; 31 int sum[MAX_N]; 32 33 int shortest(){ 34 int minn = INF; 35 int rt = -1; 36 for(int v=0; v dis[u] + G[u][v]){ 68 pathNum[v] = pathNum[u]; 69 dis[v] = dis[u] + G[u][v]; 70 path[v] = u;//记录前驱 71 sum[v] = sum[u] + a[v];//更新顶点上的权值和 72 }else if(dis[v] == dis[u] + G[u][v]){ //这部分是关键，同值不同解 73 //cout << "same " << u << endl; 74 pathNum[v] += pathNum[u];//|Tv| += |Tu| 这一步是关键 75 if(sum[v] < sum[u] + a[v]){ 76 sum[v] = sum[u] + a[v]; 77 path[v] = u; 78 } 79 } 80 //cout << "path[" << v << "] = " << path[v] << endl; 81 } 82 } 83 } 84 85 void init(){ 86 for(int u=0; u
sta;117 int cur = d;118 sta.push(cur);119 while(cur != s){120 cur = path[cur];121 sta.push(cur);122 }123 while(sta.size() > 1){124 printf("%d ", sta.top());125 sta.pop();126 }127 printf("%d", sta.top());128 return 0;129 }