題目鏈接：點擊查看

題目大意：給出一個無向圖，再給出起點和終點，要求消防隊員從起點出發(fā)，盡可能快的趕往終點，每個點都有一個權值w，代表該點有多少個人口，問消防隊員在盡可能快的趕到終點的前提下，一共有多少條路徑可以選擇，并且沿路最多能招募多少人口

題目分析：說白了就是一道裸的迪杰斯特拉，然后用動態(tài)規(guī)劃維護有多少條最短路，以及單條最短路上的最大點權之和，不過我不會。。動態(tài)規(guī)劃真的是愁人，看了網(wǎng)上的題解后就豁然開朗，只需要開兩個dp維護上面說到的兩個狀態(tài)即可，dp1[i]記錄經(jīng)過點i的最短路有幾條，dp2[i]記錄經(jīng)過點i的最多人數(shù)有多少，轉移方程的話放到迪杰斯特拉中的松弛操作中同步進行：

if(d[v]>d[u]+w)//當點u可以更新點v時，同步更新dp1和dp2 {dp1[v]=dp1[u];dp2[v]=dp2[u]+a[v]; } else if(d[v]==d[u]+w)//當點u與點v的權值相當時，將點u的狀態(tài)轉移到點v中去 {dp1[v]+=dp1[u];dp2[v]=max(dp2[v],dp2[u]+a[v]); }

簡單線性dp，應該不難理解，就不過多贅述了

實現(xiàn)代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=550;struct Node {int to,w;Node(int TO,int W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;} }; vector<Node>node[N];int dp1[N],dp2[N];//dp1:記錄經(jīng)過該點的最短路有幾條 dp2:記錄經(jīng)過該點的最多人數(shù)有多少 int d[N];int a[N];void Dijkstra(int x) {memset(d,inf,sizeof(d));d[x]=0;dp1[x]=1;dp2[x]=a[x];priority_queue<Node>q;q.push(Node(x,0));while(!q.empty()){Node cur=q.top();q.pop();int u=cur.to;if(d[u]!=cur.w)continue;for(int i=0;i<node[u].size();i++){int v=node[u][i].to;int w=node[u][i].w;if(d[v]>d[u]+w){d[v]=d[u]+w;dp1[v]=dp1[u];dp2[v]=dp2[u]+a[v];q.push(Node(v,d[v]));}else if(d[v]==d[u]+w){dp1[v]+=dp1[u];dp2[v]=max(dp2[v],dp2[u]+a[v]);}}} }int main() { // freopen("input.txt","r",stdin);int n,m,st,ed;scanf("%d%d%d%d",&n,&m,&st,&ed);for(int i=0;i<n;i++)scanf("%d",a+i);while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);node[u].push_back(Node(v,w));node[v].push_back(Node(u,w));}Dijkstra(st);cout<<dp1[ed]<<' '<<dp2[ed]<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的PAT (Advanced Level) 1003 Emergency(最短路+动态规划)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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