7-4 城市间紧急救援 (25 分)
#include <iostream> #include<bits/stdc++.h> using namespace std; const int inf =0x3f3f3f3f; map<string,int>mp; map<int,string>name; int dist[600],vis[600]; int dist2[600],dist3[600],n; int tu[600][600],w[600][600]; int cnt =0; int Kill[600]; int id(string h){ if(mp.count(h)){ return mp[h]; } else{ mp[h] = cnt++; name[cnt-1] = h; return cnt-1; } } int pre[600],Num[600]; void dijkstra(int s){ memset(dist,inf,sizeof dist); memset(dist2,0,sizeof dist2); memset(dist3,0,sizeof dist3); memset(Num,0,sizeof Num); memset(vis,0,sizeof vis); memset(pre,-1,sizeof pre); dist[s] =0; Num[s] = 1; dist3[s] =0; while(1){ int x =-1,Min =inf; for(int i=0;i<n;i++) { if(!vis[i]&&Min>dist[i]){ Min = dist[i]; x =i; } } if(x==-1)break; vis[x] = 1; for(int i=0;i<n;i++){ if(!vis[i]){ if(dist[i]>dist[x]+tu[x][i]){ dist[i] = dist[x]+tu[x][i]; // dist2[i] = dist2[x]+w[x][i]; //dist2[i] = dist2[x]+1; Num[i] = Num[x]; dist3[i] = dist3[x]+Kill[x]; pre[i] = x; } else if(dist[i]==dist[x]+tu[x][i]){ // if(dist2[i]>dist2[x]+w[x][i]){ // // dist2[i] = dist2[x]+w[x][i]; // } Num[i]+=Num[x]; if(dist3[i]<dist3[x]+Kill[x]){ dist3[i] = dist3[x]+Kill[x]; pre[i] = x; } } } } } } int main() { int m,s,d; cin>>n>>m>>s>>d; // string ss,dd; // cin>>ss>>dd; for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ if(i==j)continue; tu[i][j] = inf; w[i][j]=inf; } } int u,v,l,ww; for(int i=0;i<n;i++){ cin>>Kill[i]; } // for(int i=1;i<=m;i++){ // // string s1,s2; // int num; // cin>>s1>>s2>>num; // int i1 = id(s1); // int i2 = id(s2); // tu[i1][i2]= tu[i2][i1] = num; // } for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&l); tu[u][v] = tu[v][u] = min(tu[u][v],l); // w[u][v]= w[v][u] = ww; } dijkstra(s); int pp = d; int ans =0; stack<int>aa; while(pp!=-1){ ans+=Kill[pp]; aa.push(pp); pp = pre[pp]; } int top =1; //printf("\n"); // if(tu[s][d]==dist[d]){ // Num[d]++; // } //for(int i=1;i<=n;i++){ // // cout<<dist3[i]<<" "<<endl; //} //cout<<endl; cout<<Num[d]<<" "<<ans<<endl; while(!aa.empty()){ int k; k = aa.top(); aa.pop(); if(top)top=0; else printf(" "); cout<<k; } //cout<<dist[d]<<" "<<dist2[d]<<endl; return 0; }