眾所周知，Dijkstra經常拿來解決不帶負權和環的單元最短路。我們先來看一下他的實現過程

(由于樸素版用的不多，我們直接上堆優化)

模板

#include<bits/stdc++.h> 
#define mf(x,y) make_pair(x,y)//x距離，y節點 
using namespace std; 
int read(){int s=0,fl=1;char w=getchar();while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();}while(w<='9'&&w>='0'){s=s*10+(w^48);w=getchar();}return fl*s;
}
const int N=1000010;
int n,m,s,tot;
int head[N],ne[N],to[N],w[N];
void add(int x,int y,int ww){to[++tot]=y;ne[tot]=head[x];head[x]=tot;w[tot]=ww;  
}  
int d[N];
bool book[N];
void dj(int s){for(int i=1;i<=n;i++){d[i]=2147483647;}d[s]=0;priority_queue<pair<int,int> >q;q.push(mf(0,s)); // 將源點及其距離為0的信息加入隊列  while(!q.empty()){  int x=q.top().second;q.pop(); // 取出距離最小的節點  if(book[x]){continue; // 如果節點已被訪問過，則跳過 }book[x]=1; // 標記節點為已訪問  for(int i=head[x];i;i=ne[i]){ // 遍歷當前節點的所有鄰接節點  int y=to[i]; // 鄰接節點的編號if(d[y]>w[i]+d[x]){ // 如果通過當前節點可以找到更短的路徑  d[y]=d[x]+w[i]; // 更新最短路徑長度  q.push(mf(-d[y],y)); // 將鄰接節點及其新的距離（取反后）加入隊列  }}}
}
int main(){  n=read(),m=read(),s=read();for(int i=1,u,v,ww;i<=m;i++){u=read(),v=read(),ww=read();add(u,v,ww);}dj(s);for(int i=1;i<=n;i++){printf("%d ",d[i]);}cout<<endl;return 0; 
}

題目1? P4568 [JLOI2011] 飛行路線 - 洛谷

據題目可知，就是把每個城市看作一個節點，每條航線為一個邊，機票費用為邊權。要求在k此免費(也就是直接去一個城市而不用給機票費用)的情況下，從s飛到t

先考慮免費這個東西怎么處理。免費我們可以看作從節點1到節點2的邊權為0。簡單來說，我們可以建立層圖

可以把這個多層圖想象成「多層停車場」，每一層對應一個「權限使用次數」，幫你理解這段代碼的作用：

• 假設你要從起點開車到終點，停車場有?k+1?層（編號 0 到 k），每層對應 “使用了?j?次免費通行權限” 的狀態（比如 j=0 表示一次沒用到，j=1 表示用了 1 次，最多用到 j=k 次）。
• 原始道路：每一層內部有普通道路，走一次要花?c?元（對應代碼里同層邊的權重?c）。
• 免費通道：層與層之間有 “免費電梯”，從第?j?層到第?j+1?層可以免費換乘（對應跨層邊的權重 0），但每次換乘會消耗一次免費次數（所以最多到第 k 層）。

來看建圖的代碼：

int main(){n=read();m=read();k=read();s=read();t=read();for(int i=1;i<=m;i++){int a,b,c;a=read();b=read();c=read();for(int j=0;j<=k;j++){add(a+j*n,b+j*n,c);add(b+j*n,a+j*n,c);if(j<k){add(a+j*n,b+(j+1)*n,0);add(b+j*n,a+(j+1)*n,0);}}}

a為起點，b為終點，c為權值。內層的for循環建立了k層圖，也就是有多少免費次數就建多少層。因為第i層對應的是使用i次免費特權時圖。

if嵌套外面的語句負責建立最基礎的聯通關系，提供基礎信息

當j<k，代表免費次數沒有用完，那么就在第j*n層和下一層建立一條邊權為0的邊，也就是當前層的每一個點都有免費通行到下一層的權利。

Dijkstra部分

當我們建完多層圖后，就可以直接跑dijkstra了

void dj(int s){memset(d,0x7f,sizeof(d));d[s]=0;priority_queue<pair<int,int> >q;q.push(mf(0,s));while(!q.empty()){  int x=q.top().second;int p=q.top().first;q.pop();if (p>d[x]) continue;if(book[x]){continue;}book[x]=1;for(int i=head[x];i;i=ne[i]){  int y=to[i];if(d[y]>w[i]+d[x]){  d[y]=d[x]+w[i];q.push(mf(-d[y],y)); }}}
}

沒啥可說的

AC代碼

#include<bits/stdc++.h>
#define mf(x,y) make_pair(x,y)//x距離，y節點 using namespace std;
const int N=5000100;
int read(){int s=0,fl=1;char w=getchar();while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();}while(w<='9'&&w>='0'){s=s*10+(w^48);w=getchar();}return fl*s;
}
void out(int x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else out(x/10),putchar(x%10+'0');
}
int n,m,k,s,t;
int tot;
int head[N],ne[N],to[N],w[N];
void add(int x,int y,int ww){to[++tot]=y;ne[tot]=head[x];head[x]=tot;w[tot]=ww;  
}  
int d[N];
bool book[N];
void dj(int s){memset(d,0x7f,sizeof(d));d[s]=0;priority_queue<pair<int,int> >q;q.push(mf(0,s));while(!q.empty()){  int x=q.top().second;int p=q.top().first;q.pop();if (p>d[x]) continue;if(book[x]){continue;}book[x]=1;for(int i=head[x];i;i=ne[i]){  int y=to[i];if(d[y]>w[i]+d[x]){  d[y]=d[x]+w[i];q.push(mf(-d[y],y)); }}}
}int main(){n=read();m=read();k=read();s=read();t=read();for(int i=1;i<=m;i++){int a,b,c;a=read();b=read();c=read();for(int j=0;j<=k;j++){add(a+j*n,b+j*n,c);add(b+j*n,a+j*n,c);if(j<k){add(a+j*n,b+(j+1)*n,0);add(b+j*n,a+(j+1)*n,0);}}}dj(s);int ans=1e18;for(int j=0;j<=k;j++){ans=min(ans,d[t+j*n]);}out(ans);return 0;
}

題目2

P1948 [USACO08JAN] Telephone Lines S - 洛谷

OK國際慣例，先來騙個分

不錯，下面進入正題

據題可知，我們的目的只是把1號和n連起來。和上一道題一樣，有k此免費連的機會。于是建圖其實時差不多的。

signed main(){n=read();p=read();k=read();for(int i=1;i<=p;i++){int x,y,v;x=read();y=read();v=read();for(int j=0;j<=k;j++){add(x+j*n,y+j*n,v);add(y+j*n,x+j*n,v);if(j<k){add(x+j*n,y+(j+1)*n,0);add(y+j*n,x+(j+1)*n,0);				}}}

Dijkstra部分

void dj(int s){memset(d,0x7f,sizeof(d));d[s]=0;priority_queue<pair<int,int> >q;q.push(mf(0,s));while(!q.empty()){int x=q.top().second;int p=q.top().first;q.pop();if(book[x]) continue;book[x]=1;for(int i=head[x];i;i=ne[i]){int y=to[i];int np=max(-p,w[i]);if(d[y]>np){d[y]=np;q.push(mf(-d[y],y));}}}
}

和之前一題也差不多，但是不是求最短路，而是求當前的代價和連這條電線的最大值和y節點的最小值的最小值（？）

不過做這道題一定一定要注意數組大小，當時我就是數組開小了調了半天

AC代碼

#include<bits/stdc++.h>
#define mf(a,b) make_pair(a,b)
#define int long long
using namespace std;
const int N=5000010;
int read(){int s=0,fl=1;char w=getchar();while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();}while(w<='9'&&w>='0'){s=s*10+(w^48);w=getchar();}return fl*s;
}
void out(int x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else out(x/10),putchar(x%10+'0');
}
int n,p,k;
int head[N],ne[N],to[N],w[N],d[N],book[N];
int tot;
void add(int x,int y,int v){to[++tot]=y;ne[tot]=head[x];head[x]=tot;w[tot]=v;
}
void dj(int s){memset(d,0x7f,sizeof(d));d[s]=0;priority_queue<pair<int,int> >q;q.push(mf(0,s));while(!q.empty()){int x=q.top().second;int p=q.top().first;q.pop();if(book[x]) continue;book[x]=1;for(int i=head[x];i;i=ne[i]){int y=to[i];int np=max(-p,w[i]);if(d[y]>np){d[y]=np;q.push(mf(-d[y],y));}}}
}
signed main(){n=read();p=read();k=read();for(int i=1;i<=p;i++){int x,y,v;x=read();y=read();v=read();for(int j=0;j<=k;j++){add(x+j*n,y+j*n,v);add(y+j*n,x+j*n,v);if(j<k){add(x+j*n,y+(j+1)*n,0);add(y+j*n,x+(j+1)*n,0);				}}}dj(1);int ans=2e9;for(int i=0;i<=k;i++){ans=min(ans,d[n+i*n]);}out(ans==2e9?-1:ans);return 0;
}