題目鏈接：點擊查看

題目大意：在郊區有N座通信基站，P條雙向電纜，第i條電纜連接基站Ai和Bi。特別的，1號基站是通信公司的總站，N號基站位于一座農場中。現在，農場主希望對通信線路進行升級，其中升級第i條電纜需要花費Li

電話公司正在舉行優惠活動，農場主可以指定一條從1號基站到N號基站的路徑，并指定路徑上不超過K條電纜，由電話公司免費提供升級服務，農場主只需要支付在該路徑上剩余的電纜中，升級價格最貴的那條電纜的花費即可，求至少用多少錢能完成升級

題目分析：因為是要求最短路中權值最大值的最小值，不難讓人想到二分，但這個題目我更想練一下分層圖最短路的模板，大概就是spfa迭代更新dp的狀態，dp[i][j]代表起點到點i，一路上免費了j個電纜后的答案，因為免費k條是最優的，所以答案就是d[n][k]了

代碼：

#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> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;//頂點數 const int M=2e5+100;//邊數 struct Edge {int to,w,next; }edge[M];int head[N],d[N][N],cnt;//鏈式前向星 d[i][j]:從st點到i點，途中已經免費了j條后，路上邊權的最大值 bool vis[N][N];//vis[i][j]:與d[i][j]同步記錄當前(i,j)狀態是否遍歷 void addedge(int u,int v,int w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++; }struct Node {int to,c,w;//c表示免費了幾條邊 Node(int TO,int W,int C){to=TO;w=W;c=C;}bool operator<(const Node& a)const{return w>a.w;} };void spfa(int st,int k)//k:免費了k條路 {memset(vis,false,sizeof(vis));memset(d,-1,sizeof(d));d[st][0]=0;priority_queue<Node>q;q.push(Node(st,0,0));//點，權，免費的c while(q.size()){Node cur=q.top();q.pop();int u=cur.to;int c=cur.c;if(vis[u][c])continue;vis[u][c]=true;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;if(!vis[v][c]&&(d[v][c]==-1||d[v][c]>max(d[u][c],w))){d[v][c]=max(d[u][c],w);q.push(Node(v,d[v][c],c));}if(c<k){if(!vis[v][c+1]&&(d[v][c+1]==-1||d[v][c+1]>d[u][c])){d[v][c+1]=d[u][c];q.push(Node(v,d[v][c+1],c+1));}}}} }void init() {memset(head,-1,sizeof(head));cnt=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m,k;while(scanf("%d%d%d",&n,&m,&k)!=EOF){init();while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);addedge(v,u,w);}spfa(1,k);printf("%d\n",d[n][k]);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3662 Telephone Lines(分层图最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。