題目鏈接：點擊查看

題目大意：給出一張圖，每條邊都有權值，現(xiàn)在要求從點st到達點ed，沿途中可以讓k條邊的邊權免費，現(xiàn)在求最短路

題目分析：分層圖經(jīng)典模板問題，直接套板子就行了，最后記得對于數(shù)組d的每一項中找出最小值作為答案

代碼：

#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=1e4+100;//頂點數(shù) const int M=1e5+100;//邊數(shù) struct Edge {int to,w,next; }edge[M];int head[N],d[N][15],cnt;//鏈式前向星 d[i][j]:從st點到i點，途中已經(jīng)免費了j條后，路上邊權的最大值 bool vis[N][15];//vis[i][j]:與d[i][j]同步記錄當前(i,j)狀態(tài)是否遍歷 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 Dijkstra(int st,int k) {priority_queue<Node>q; memset(vis,false,sizeof(vis));memset(d,inf,sizeof(d));d[st][0]=0;q.push(Node(st,0,0));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(d[v][c]>d[u][c]+w){d[v][c]=d[u][c]+w;q.push(Node(v,d[v][c],c));}if(c==k)continue;if(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;scanf("%d%d%d",&n,&m,&k);init();int st,ed;scanf("%d%d",&st,&ed);while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);addedge(v,u,w);}Dijkstra(st,k);int ans=inf;for(int i=0;i<=k;i++)ans=min(ans,d[ed][i]);printf("%d\n",ans); return 0; }

?

總結

以上是生活随笔為你收集整理的洛谷 - P4568 [JLOI2011]飞行路线(分层图最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

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