//一开始/*amount[start] = team[start];dist[start] = 0;pathcount[start] = 1;u = 0;dist[1] = dist[0] + map[0][1]; // dist[1] == 1dist[2] = dist[0] + map[0][1]; // dist[2] == 2amount[1] = 1 + 2;pathcount[1] = 1;pathcount[2] = 1;u = 1;dist[1] + map[1][2] == 2;//满足dist[2] == dist[1] _ map[1][2];pathcount[2] = 1 + 1;//此时amount[2] = 0,amount[1] == 3,team[2] == 1;//soamount[2] = 3 + 1;....此时0~2的最短距离和0~2的所有team数目已经求出来了，分别是pathcount[2],amount[2]*/#include <cstdio>#include <iostream>#include <cstdlib>using namespace std;const int MX = 500 + 5;const int INF = 9999999;int map[MX][MX];//记录两个点之间的距离sint dist[MX];//记录从起始点到点i的距离int teams[MX];//记录每个城市的队伍数量int amount[MX];//记录起始点到当前点的最大队伍数量int pathcount[MX];//记录从起始点到当前点点的最短路径数量int v[MX];//标记是否被访问过int N,M,start,en,dmin;void dijkstra(int start) { amount[start] = teams[start]; dist[start] = 0; pathcount[start] = 1; while (1){ int u,dmin = INF; //都是从0开始，因为第一遍循环会把起始点找出来 for (int i = 0; i < N; i++){ if (v[i] == 0 && dist[i] < dmin){ dmin = dist[i]; u = i; } } //dmin==INF表示所有点已经都遍历过了 if (dmin == INF) break; //将找到的点标记一下，说明这个点已经访问过，之后就不要访问了 v[u] = 1; for (int i = 0; i < N; i++) { if (v[i] == 0) { if (dist[i] > dist[u] + map[u][i]) { dist[i] = dist[u] + map[u][i]; amount[i] = amount[u] + teams[i]; pathcount[i] = pathcount[u]; } else if (dist[i] == dist[u] + map[u][i]) { //如果距离相等就，到达当前的最短路径数就加1 pathcount[i] += pathcount[u]; //如果之前的最大队伍数量小于现在的队伍数量，则进行更新 if (amount[i] < amount[u] + teams[i]){ amount[i] = amount[u] + teams[i]; } } } } } }int main() { while (~scanf("%d%d%d%d",&N,&M,&start,&en)) { for (int i = 0; i < N; i++) { cin >> teams[i]; } //初始化map数组 for (int i = 0; i < N; i++) { dist[i] = INF; for (int j = 0; j < N; j++) { map[i][j] = INF; } } //读入数据 for (int i = 0; i < M; i++) { int c1,c2,L; cin >> c1 >> c2 >> L; map[c1][c2] = map[c2][c1] = L; } //对所有点进行松弛 dijkstra(start); cout << pathcount[en] << " " << amount[en] << endl; } system("pause"); return 0;}
新闻热点
疑难解答
