L2-001 緊急救援

分數 25

作為一個城市的應急救援隊伍的負責人，你有一張特殊的全國地圖。在地圖上顯示有多個分散的城市和一些連接城市的快速道路。每個城市的救援隊數量和每一條連接兩個城市的快速道路長度都標在地圖上。當其他城市有緊急求助電話給你的時候，你的任務是帶領你的救援隊盡快趕往事發地，同時，一路上召集盡可能多的救援隊。

輸入格式:

輸入第一行給出4個正整數N、M、S、D，其中N（2≤N≤500）是城市的個數，順便假設城市的編號為0 ~?(N?1)；M是快速道路的條數；S是出發地的城市編號；D是目的地的城市編號。

第二行給出N個正整數，其中第i個數是第i個城市的救援隊的數目，數字間以空格分隔。隨后的M行中，每行給出一條快速道路的信息，分別是：城市1、城市2、快速道路的長度，中間用空格分開，數字均為整數且不超過500。輸入保證救援可行且最優解唯一。

輸出格式:

第一行輸出最短路徑的條數和能夠召集的最多的救援隊數量。第二行輸出從S到D的路徑中經過的城市編號。數字間以空格分隔，輸出結尾不能有多余空格。

輸入樣例:

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

題解

根據題意，很容易想到這是要用最短路算法，但求的不是最短路徑，而是最短路的數目和一堆奇奇怪怪的東西。

最短路的數目可以在判斷最短路的時候就加上去，詳見洛谷P1144最短路計數。

題目還要求在路徑最短的同時還要救援隊最多，那么在遇到兩個同樣長的路徑時，判斷哪條路的救援隊加起來更多，以此作為判斷依據來更新路徑。

最后記錄一整條路徑，輸出就好了。?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=1e9;
const int N=505;
ll n,m,s,d;
ll dis[N],vis[N];//dis是起點到i點的最短路徑
ll jy[N];
ll ms[N];//最短路徑條數
ll maxjy[N];//沒用上
ll fa[N];//記錄該點的父節點
ll ans[N];//當前點最多的救援隊數量
ll sum;
vector<pair<int,int> > g[N];//用vector存圖
vector<ll> path;//存放路徑
ll out[N];
//迪杰斯特拉算法
void Dij(ll s)
{for(int i=0;i<n;i++){dis[i]=inf;}dis[s]=0;priority_queue<pair<ll,int> > q;for(int i=0;i<n;i++){q.push(make_pair(-dis[i],i));}while(!q.empty()){int u=q.top().second;q.pop();if(vis[u]==1) continue;vis[u]=1;for(int i=0;i<g[u].size();i++){int v=g[u][i].first;int w=g[u][i].second;if(dis[v]>dis[u]+w)//是最短路就更新{dis[v]=dis[u]+w;ms[v]=ms[u];fa[v]=u;ans[v]=ans[u]+jy[v];q.push(make_pair(-dis[v],v));}else if(dis[v]==dis[u]+w)//遇到同樣短的路{ms[v]+=ms[u];if(ans[v]<ans[u]+jy[v])//判斷誰的救援隊多{fa[v]=u;//更新ans[v]=ans[u]+jy[v];}}}}
}
//記錄路徑
void getPath(ll s,ll d)
{path.push_back(d);while(d!=s){d=fa[d];path.push_back(d);}reverse(path.begin(),path.end());int i=0;for(auto k:path){i++;out[i]=k;}
}
int main()
{cin>>n>>m>>s>>d;for(int i=0;i<n;i++){cin>>jy[i];}while(m--){int x,y,w;cin>>x>>y>>w;//雙向存圖g[x].push_back(make_pair(y,w));g[y].push_back(make_pair(x,w));}//初始化ms[s]=1;ans[s]=jy[s];Dij(s);getPath(s,d);//輸出cout<<ms[d]<<" ";cout<<ans[d]<<endl;for(int i=1;i<=path.size()-1;i++){cout<<out[i]<<" ";}cout<<out[path.size()]<<endl;return 0;
}