<題目鏈接>

題目大意：

作為一個城市的應急救援隊伍的負責人，你有一張?zhí)厥獾娜珖貓D。在地圖上顯示有多個分散的城市和一些連接城市的快速道路。每個城市的救援隊數(shù)量和每一條連接兩個城市的快速道路長度都標在地圖上。當其他城市有緊急求助電話給你的時候，你的任務是帶領你的救援隊盡快趕往事發(fā)地，同時，一路上召集盡可能多的救援隊。

輸入格式：

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

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

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

解題分析：

由于本題在保證路徑最短的情況下，還要使路徑上的點權(quán)和最大，所以我們在最短路的松弛過程中，優(yōu)先松弛路徑，如果最短路徑相同，再考慮挑選點券和最大的路，并且，最短路的條數(shù)也能夠在Dijkstra松弛的過程中維護。

#include <bits/stdc++.h> using namespace std;const int N = 505; const int INF = 0x3f3f3f3f; #define pb push_back int n,m,st,ed; struct Edge{ int to,val; }; vector<Edge>G[N]; int path[N],vis[N],num[N];struct Node{int loc,dist,mxval,cnt;Node(int _loc=0,int _dist=0,int _mxval=0,int _cnt=0):loc(_loc),dist(_dist),mxval(_mxval),cnt(_cnt){}bool operator < (const Node &tmp)const{return dist>tmp.dist;} }node[N];void Dij(){memset(path,-1,sizeof(path));for(int i=0;i<n;i++){vis[i]=0,node[i]=Node(i,INF,0,0);}priority_queue<Node>q;node[st]=Node(st,0,num[st],1);q.push(node[st]);while(!q.empty()){int u=q.top().loc;q.pop();if(vis[u])continue;vis[u]=1;for(int i=0;i<G[u].size();i++){int v=G[u][i].to,cost=G[u][i].val;if(node[v].dist>node[u].dist+cost){node[v].dist=node[u].dist+cost;path[v]=u; //記錄上一個點node[v].cnt=node[u].cnt; //更新這個點的最短路條數(shù)node[v].mxval=node[u].mxval+num[v]; //記錄以這個點為終點的最短路的點權(quán)和 q.push(node[v]);}else if(node[v].dist==node[u].dist+cost){ node[v].cnt+=node[u].cnt; //因為有多條最短路徑，所以這里將之前的最短路徑條數(shù)加起來 if(node[v].mxval<node[u].mxval+num[v]){ //更新最短路徑上的點權(quán)最小值 node[v].mxval=node[u].mxval+num[v];path[v]=u;}}}} }void Print(int u){ //遞歸打印路徑 if(u==st){printf("%d",st);return;}Print(path[u]);printf(" %d",u); }int main(){scanf("%d%d%d%d",&n,&m,&st,&ed);for(int i=0;i<n;i++)scanf("%d",&num[i]);for(int i=0;i<m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);G[u].pb(Edge{v,w});G[v].pb(Edge{u,w});}Dij();printf("%d %d\n",node[ed].cnt,node[ed].mxval);Print(ed);puts("");return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/00isok/p/10575027.html

總結(jié)

以上是生活随笔為你收集整理的PTA L2-001 紧急救援 (点带权最短路)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。