本题的题意：给定 n 个城市和 m 条连接城市的道路，每座城市都有相应的权值。计算从 c1 城市到 c2 城市最短路的条数 t，并在最短路的情况下，并计算 t 座城市路径权值的最大值。
解题思路：本题采用 Dijkstra 算法，进行相应的改变，即可完成题目解答。其中，部分细节已在代码中有所注释。
题目链接：https://www.patest.cn/contests/pat-a-practise/1003
#include <iostream> #include <algorithm> #include <map> #include <stack> #include <queue> #include <vector> #include <set> using namespace std; const int CITY_NUM = 505; const int INF = 1<<30; typedef struct CityInfo//City的信息 { int numPath,teams,sum,lowcost; bool visited; }CityInfo; CityInfo CC[CITY_NUM]; int GMap[CITY_NUM][CITY_NUM];//邻接矩阵 void init()//一些初始化 { for(int i=0;i<CITY_NUM;++i) { CC[i].visited = false; CC[i].sum = 0; CC[i].numPath = 0; CC[i].lowcost = INF; for(int j=0;j<CITY_NUM;++j) GMap[i][j] = INF; } } void dijk(int c1,int n) { //对起始点做一些单独的设定 int u = c1; CC[u].sum = CC[u].teams; CC[u].numPath = 1; CC[u].lowcost = 0; for(int i=0;i<n;++i) { CC[u].visited = true; //更新点周围相邻点的信息 for(int j=0;j<n;++j) { if(CC[u].lowcost + GMap[u][j] < CC[j].lowcost && CC[j].visited == false) { CC[j].lowcost = CC[u].lowcost + GMap[u][j]; CC[j].sum = CC[u].sum + CC[j].teams; CC[j].numPath = CC[u].numPath;//注意点：路径条数是继承上一点的条数的，而不是 1 } else if(CC[u].lowcost + GMap[u][j] == CC[j].lowcost && CC[j].visited == false) { CC[j].numPath += CC[u].numPath;//同样的注意点，而不是自增这么简单 if(CC[u].sum + CC[j].teams > CC[j].sum) { CC[j].sum = CC[u].sum + CC[j].teams;//计算出权值最大 } } } int min = INF,pos; for(int j=0;j<n;++j)//找下一个节点 { if(min > CC[j].lowcost && CC[j].visited == false) { min = CC[j].lowcost; pos = j; } } u = pos; } } int main(int argc, char** argv) { int n,m,c1,c2; cin >> n >> m >> c1 >> c2; init(); for(int i=0;i<n;++i) { cin >> CC[i].teams; } for(int i=0;i<m;++i) { int x1,x2,dis; cin >> x1 >> x2 >> dis; GMap[x1][x2] = dis; GMap[x2][x1] = dis; } dijk(c1,n); cout << CC[c2].numPath << " " << CC[c2].sum << endl; return 0; }
