天梯赛城市间紧急救援

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

输入格式:

输入第一行给出4个正整数

第二行给出

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从

输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3

菜鸡的成长史

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=505,INF=0x3f3f3f3f;
 4 int vis[N],pre[N],sum[N],dis[N],num[N],in[N];
 5 int n,m,s,d; //vis标记,pre记录路径,sum记录兵队数,dis到起始点的距离,num最短路径条数
 6 vector<pair<int,int> > G[N];
 7 struct node
 8 {
 9     int B,J;
10     bool operator <(const node &x) const
11     {
12         return x.J<J;
13     }
14 }p,q;
15 void dij()
16 {
17     priority_queue<node> que;  //省去了查找最短距离
18     for(int i=0;i<N;i++) dis[i]=INF,pre[i]=-1;
19     que.push({s,0});   //到起始点的距离 编号和距离
20     dis[s]=0,sum[s]=in[s],num[s]=1;
21     while(!que.empty())
22     {
23         p=que.top(),que.pop();
24         int u=p.B,v,w;
25         if(vis[u]) continue;
26         vis[u]=1;
27         for(auto X:G[u])
28         {
29             v=X.first,w=X.second;dis[v]
30             if(dis[v]>p.J+w)
31                 dis[v]=p.J+w,sum[v]=sum[u]+in[v],num[v]=num[u],pre[v]=u,q.B=v,q.J=dis[v],que.push(q);
32             else if(dis[v]==p.J+w)
33             {
34                 if(sum[v]<sum[u]+in[v])
35                     sum[v]=sum[u]+in[v],pre[v]=u;
36                 num[v]+=num[u];
37             }
38         }
39     }
40 
41 }
42 int main()
43 {
44     ios::sync_with_stdio(false);
45     cin>>n>>m>>s>>d;
46     for(int i=0;i<n;i++) cin>>in[i];
47     for(int i=0,d1,d2,d3;i<m;i++)
48     {
49         cin>>d1>>d2>>d3;
50         G[d1].push_back({d2,d3});  //建图
51         G[d2].push_back({d1,d3});
52     }
53     dij();
54     cout << num[d] << " " << sum[d] << endl;
55     vector<int> vec;
56     int pos=d;
57     while(pos!=-1) vec.push_back(pos),pos=pre[pos];
58     for(int i=vec.size()-1;i>=0;i--)
59     {
60         if(i!=vec.size()-1) cout << " ";
61         cout << vec[i];
62     }
63     cout << endl;
64     return 0;
65 }

View Code

天梯赛 城市间紧急救援

输入格式:

输出格式:

输入样例:

输出样例:

天梯赛城市间紧急救援