首页 > 代码库 > 【PAT L2-001】最短路计数
【PAT L2-001】最短路计数
给定一个无向带权网络，无负边，无重边和自环，每个顶点有一个正数权值。首先求特定原点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 <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <iostream> 5 #include <algorithm> 6 #include <stack> 7 #include <cmath> 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<n; v++){ 37 if(v == s) continue; 38 if(!vis[v] && dis[v] < minn){ 39 minn = dis[v]; 40 rt = v; 41 } 42 } 43 return rt; 44 } 45 46 void dijkstra(){ 47 for(int v=0; v<n; v++){ 48 if(G[s][v] != INF && v != s){ 49 dis[v] = G[s][v];//一步直达 50 path[v] = s; 51 pathNum[v] = 1; 52 sum[v] = a[s] + a[v]; 53 } 54 } 55 path[s] = -1; 56 pathNum[s] = 1; 57 vis[s] = 1; 58 sum[s] = a[s]; 59 dis[s] = 0; 60 while(1){ 61 int u = shortest();//select the next vertex 62 if(u == -1) break;//no vertex left 63 //cout << "choose " << u << endl; 64 vis[u] = 1; 65 for(int v=0; v<n; v++){//update priority 66 if(vis[v]) continue;//只考虑Tk以外，即最短路尚未确定的点 67 if(dis[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<n; u++){ 87 for(int v=0; v<n; v++){ 88 G[u][v] = INF; 89 } 90 G[u][u] = 0; 91 dis[u] = INF; 92 } 93 CLEAR(path, -1); 94 CLEAR(pathNum, 0); 95 CLEAR(sum, 0); 96 CLEAR(vis, 0); 97 } 98 99 int main()100 {101 FREAD();102 scanf("%d%d%d%d", &n, &m, &s, &d);103 init();104 REP(n) RINT(a[i]);105 REP(m){106 int u, v, w;107 scanf("%d%d%d", &u, &v, &w);108 G[u][v] = min(G[u][v], w);//其实没有重边109 G[v][u] = G[u][v];//邻接矩阵110 }111 112 dijkstra();//s为源, d为目的地113 printf("%d %d\n", pathNum[d], sum[d]);114 115 //输出路径116 stack<int> 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 }
【PAT L2-001】最短路计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。