题目大意：n个城市，m条路径，每条路径有个距离值，每个城市有一个权重值vi,随意给出一个起点s和终点e，求出从s到e的最短路径的同时，尽可能保证路径上的城市的权重和最大。用prime算法求最短路径的同时，实时更新每个城市的最大权重和以及走到该城市的可能数。
#include <iostream> #include <vector> #include <cstdio> using namespace std; #define maxn 505 bool vis[maxn]; //vis[i]标记是否已经确定了从起点到城市i的路径 int fa[maxn]; //fa[i]表示i城市的上一个城市下标 int w[maxn]; //w[i]表示走到i城市的路径上的权重和 int d[maxn]; //d[i]表示从起点走到i城市的最短距离 int c[maxn]; //c[i]表示走到i城市的可能数 typedef struct edge{ int from,to,dist; }Edge; vector<int> city[maxn]; //保存每个节点的边 vector<int> pres[maxn]; //保存相同距离下所有前驱的节点 Edge edges[maxn*maxn]; int count = 0; int n,m,s,e; //建边 void build_edges(int from,int to,int dist){ edges[count].dist = dist; edges[count].from = from; edges[count].to = to; city[from].push_back(count); count ++; } int dfs(int x){ for(int i =0;i < city[x].size();i ++){ int t = city[x][i]; int to = edges[t].to; int dist = edges[t].dist; if(dist + d[x] == d[to]){ int pre = fa[to]; pres[to].push_back(x); //相同距离，添加该节点进前驱节点数组 if(w[x] > w[pre]){ //相同距离的，选择权重和大的作为前驱结点 w[to] += (w[x] - w[pre]); fa[to] = x; } } else if(dist + d[x] < d[to]){ d[to] = dist + d[x]; fa[to] = x; w[to] += w[x]; pres[to].clear(); //存在更短的距离，清空前驱节点数组后添加当前前驱节点 pres[to].push_back(x); } } int min_dist = 10000000; int next; //选出路径最短的（且未完成）节点 for(int i = 0;i < n;i ++){ if(!vis[i] && d[i] < min_dist){ next = i; min_dist = d[i]; } } vis[next] = true; //计算路径可能数，遍历所有前驱节点的路径数 for(int j = 0;j < pres[next].size();j ++){ c[next] += c[pres[next][j]]; } //返回节点标记，结束当前函数，而不是在这里直接dfs,避免堆栈溢出 return next; } int main() { cin >> n >> m >> s >> e; for(int i = 0;i < n;i ++){ cin >> w[i]; d[i] = 1000000000; vis[i] = false; fa[i] = -1; c[i] = 0; } for(int i = 0;i < m;i ++){ int from,to,dist; cin >> from >> to >> dist; build_edges(from,to,dist); build_edges(to,from,dist); } vis[s] = 1; d[s] = 0; c[s] = 1; while(true){ int res = dfs(s); if(res == e){ break; }else{ s = res; } }; cout << c[e] << " " << w[e]; return 0; }