在郊區(qū)有 N 座通信基站，P 條雙向電纜，第 i 條電纜連接基站AiAi和BiBi。

特別地，1 號(hào)基站是通信公司的總站，N 號(hào)基站位于一座農(nóng)場(chǎng)中。

現(xiàn)在，農(nóng)場(chǎng)主希望對(duì)通信線路進(jìn)行升級(jí)，其中升級(jí)第 i 條電纜需要花費(fèi)LiLi。

電話公司正在舉行優(yōu)惠活動(dòng)。

農(nóng)產(chǎn)主可以指定一條從 1 號(hào)基站到 N 號(hào)基站的路徑，并指定路徑上不超過 K 條電纜，由電話公司免費(fèi)提供升級(jí)服務(wù)。

農(nóng)場(chǎng)主只需要支付在該路徑上剩余的電纜中，升級(jí)價(jià)格最貴的那條電纜的花費(fèi)即可。

求至少用多少錢可以完成升級(jí)。

輸入格式

第1行：三個(gè)整數(shù)N，P，K。

第2..P+1行：第 i+1 行包含三個(gè)整數(shù)Ai,Bi,LiAi,Bi,Li。

輸出格式

包含一個(gè)整數(shù)表示最少花費(fèi)。

若1號(hào)基站與N號(hào)基站之間不存在路徑，則輸出”-1”。

數(shù)據(jù)范圍

0≤K<N≤10000≤K<N≤1000,
1≤P≤100001≤P≤10000,
1≤Li≤10000001≤Li≤1000000

輸入樣例：

5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6

輸出樣例：

4
代碼： #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<map> #include<cmath>const int N=1000000+10,M=1000000+10; typedef long long ll; using namespace std;int n,p,k; int tot=0; priority_queue< pair<int ,int> > q; struct edge {int u,v;int w;int nxt; }Edge[M]; int head[N],dis[N]; bool v[N];void add(int u,int v,int w) {Edge[++tot].u=u;Edge[tot].v=v;Edge[tot].w=w;Edge[tot].nxt=head[u];head[u]=tot; } void dijkstra() {memset(dis,0x3f3f3f3f,sizeof(dis));dis[1]=0;q.push(make_pair(0,1));while(q.size()){int x=q.top().second;q.pop();if(v[x]) continue;v[x]=true;for(int i=head[x];i;i=Edge[i].nxt){int y=Edge[i].v,z=max(Edge[i].w,dis[x]);if(dis[y]>z){dis[y]=z;q.push(make_pair(-dis[y],y));}}} }int main() {scanf("%d%d%d",&n,&p,&k);for(int i=1,x,y,z;i<=p;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);for(int j=1,z1=0;j<=k;j++){add(x+(j-1)*n,y+j*n,z1);add(y+(j-1)*n,x+j*n,z1);add(x+j*n,y+j*n,z);add(y+j*n,x+j*n,z);}}for(int i=1,z=0;i<=k;i++)add(i*n,(i+1)*n,z);dijkstra();if(dis[k+1]*n>=0x3f3f3f3f){puts("-1");}elseprintf("%d",dis[(k+1)*n]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Staceyacm/p/11319928.html

總結(jié)

以上是生活随笔為你收集整理的340. 通信线路(分层图最短路）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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