PAT L2-001. 紧急救援

题意：

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

题解：

将dijkstra改改就行，注意是稠密图，卧槽！！

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=520,inf=~0u>>2;
 6 
 7 int n,m,s,t,a[N];
 8 int mp[N][N];
 9 int vis[N],d[N],peo[N],pre[N],cnt[N];
10 
11 
12 void dij()
13 {
14     F(i,0,n-1)vis[i]=0,d[i]=inf;
15     d[s]=0;
16     pre[s]=-1;
17     cnt[s]=1,peo[s]=a[s];
18     F(i,0,n-1)
19     {
20         int mi=inf,p=-1;
21         F(j,0,n-1)if(!vis[j]&&mi>d[j])mi=d[p=j];
22         if(p==-1)continue;
23         vis[p]=1;
24         F(j,0,n-1)if(vis[j]==0&&mp[p][j]!=inf)
25         {
26             if(d[j]>d[p]+mp[p][j])
27             {
28                 d[j]=d[p]+mp[p][j];
29                 peo[j]=a[j]+peo[p];
30                 pre[j]=p;
31                 cnt[j]=cnt[p];
32             }else if(d[j]==d[p]+mp[p][j])
33             {
34                 cnt[j]+=cnt[p];
35                 if(peo[j]<a[j]+peo[p])
36                 {
37                     peo[j]=a[j]+peo[p];
38                     pre[j]=p;
39                 }
40             }
41         }
42     }
43 }
44 
45 int main()
46 {
47     scanf("%d%d%d%d",&n,&m,&s,&t);
48     F(i,0,n-1)scanf("%d",a+i);
49     F(i,0,n)F(j,0,n)mp[i][j]=(i==j?0:inf);
50     F(i,1,m)
51     {
52         int a,b,c;
53         scanf("%d%d%d",&a,&b,&c);
54         mp[a][b]=min(c,mp[a][b]);
55         mp[b][a]=mp[a][b];
56     }
57     dij();
58     printf("%d %d
",cnt[t],peo[t]);
59     int path[N],ed=0;
60     for(int i=t;~i;i=pre[i])path[++ed]=i;
61     for(int i=ed;i>0;i--)printf("%d%c",path[i],i==1?'
':' ');
62     return 0;
63 }

View Code