传送门
通过dijkstra进行数据迭代
#include <cstring>
#include <cmath>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <unordered_map>
#include <sstream>
#include <set>
#include <iomanip>using namespace std;
typedef long long ll;
stringstream ss;
const int N = 550;vector<int> path; // 存路径
int n,m,s,d;
int g[N][N]; // 邻接表存图
int dist[N]; // 到源点的最短距离
bool st[N]; // 点的状态
int c[N]; // c存储的是每个城市的救援队数目
int cnt[N], sum[N], pre[N]; // cnt表示最短路径的条数, sum表示当前路径的救援队数目, pre存储该点的前置节点void dijkstra()
{memset(dist, 0x3f, sizeof dist);// 初始化 最短距离为0 最短路径数1 救援队数为出发城市的救援队数, 前置节点置为本身dist[s] = 0, cnt[s] = 1, sum[s] = c[s], pre[s] = s;// 跌代n次(因为有n个点, 要把每个点都迭代到, 至少要进行n-1次迭代), 寻找每一个点到源点的最短距离并更新for(int i = 0; i<n; i++){int t = -1;// 找到当前与源点最近的点, 通过这个点来更新其它的点// 因为源点不一定是0所以要从下标0开始全部迭代(注意不要迭代到相同的点)for(int j = 0; j<n; j++){if(st[j] == false && (t == -1 || dist[t] > dist[j])) t = j;}st[t] = true; // 标记这个被用过的点for(int j = 0; j<n; j++){// 若距离相等, 就看谁的救援队数量更多if(st[j] == false && dist[j] == dist[t] + g[t][j]){// 最短路径数 = 原来的最短路径数量 + 当前的路径数cnt[j] += cnt[t];if(sum[j] < sum[t] + c[j]){ sum[j] = sum[t] + c[j];// 只有更新点的时候才更新前置节点pre[j] = t;}}else if(st[j] == false && dist[j] > dist[t] + g[t][j]){// 距离不等, 更新距离, 以及其他数据dist[j] = dist[t] + g[t][j];cnt[j] = cnt[t];sum[j] = sum[t] + c[j];pre[j] = t;}}}
}
int main()
{ cin>>n>>m>>s>>d;for(int i = 0; i<n; i++) cin>>c[i];memset(g, 0x3f, sizeof g);for(int i = 0; i<m; i++){int a,b,w;cin>>a>>b>>w;// 无向图g[a][b] = w;g[b][a] = w;}dijkstra();cout<<cnt[d]<<" "<<sum[d]<<endl;// 通过前置节点来输出路径int k = d;while(k != s){path.push_back(k);k = pre[k];}path.push_back(s);for(int i = path.size()-1; i>=0; i--){if(!i)cout<<path[i];else cout<<path [i]<<" ";}
}