作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。
第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
1. 4 5 0 3 2. 20 30 40 10 3. 0 1 1 4. 1 3 2 5. 0 3 3 6. 0 2 2 7. 2 3 2
结尾无空行
输出样例:
1. 2 60 2. 0 1 3
结尾无空行
#include<bits/stdc++.h> using namespace std; const int N=510,inf=0x3f3f3f3f; int pre[N],cnt[N],jyd[N],jyd_num[N],vis[N],road[N]; //pre前驱，cnt路径条数，jyd每个节点数量，jyd_num数量，vis标记 int g[N][N]; int n,m,s,d,t,k1; void dijstra(){ cnt[s]=1;//起点路径赋值 vis[s]=1;//标记 for(int i=0;i<n;i++){ int f=-1,min=inf;//F临时标记，min寻找最小路劲 for(int j=0;j<n;j++){ if(!vis[j]&&g[s][j]<min){ min=g[s][j]; f=j; } }//临时标记记录 if(f==-1)break; else vis[f]=1; for(int j=0;j<n;j++){//通过临时标记找最短路径 if(!vis[j]&&g[s][j]>g[s][f]+g[f][j]){//路径大小不同 g[s][j]=g[s][f]+g[f][j];//路径大小 jyd_num[j]=jyd_num[f]+jyd[j];//救援队数量 pre[j]=f;//前驱 cnt[j]=cnt[f];//路径条数 } else if(!vis[j]&&g[s][j]==g[s][f]+g[f][j]){//路径相同找最大救援队数量 cnt[j]+=cnt[f]; if(jyd_num[j]<jyd_num[f]+jyd[j]){ jyd_num[j]=jyd_num[f]+jyd[j]; pre[j]=f; } } } } } int main(){ cin>>n>>m>>s>>d; memset(g,inf,sizeof(g)); for(int i=0;i<n;i++){ cin>>jyd[i]; jyd_num[i]=jyd[i]; cnt[i]=1; } for(int i=0;i<m;i++){ int x,y,w; cin>>x>>y>>w; g[x][y]=g[y][x]=w; } dijstra(); cout<<cnt[d]<<' '<<jyd_num[d]+jyd[s]<<endl; t=pre[d]; k1=0; while(t!=s){//从后往前遍历 road[k1++]=t; t=pre[t]; } cout<<s; for(int i=k1-1;i>=0;i--)cout<<' '<<road[i]; cout<<' '<<d; return 0; }
