2019牛客暑期多校训练营（第四场）J：free（分层图最短路裸题）-白红宇

2019牛客暑期多校训练营（第四场）J：free（分层图最短路裸题）

阅读量：3898 次

发布时间：2019-05-23

本文共 847 字，大约阅读时间需要 2 分钟。

【题解】

题意：给定一个无向连通图，有k个让边权为0的机会，输出s到t的最短路。

思路：分层图最短路裸题。

【代码】

#include 
   
    using namespace std;const int maxn=1006;typedef pair
    
      P;const int inf=0x3f3f3f3f;int n,m,s,t,k;int d[maxn][maxn];vector 
      g[maxn];void dij(int s){    memset(d,inf,sizeof(d));    d[s][0]=0;    queue 
      q;    q.push(P(s,0)); //初始情况：0条被使用    while(!q.empty()){        int u=q.front().first,w=q.front().second;        q.pop();        for(int i=0;i
      
       d[u][w]){                d[v][w+1]=d[u][w];                q.push(P(v,w+1));            }        }    }}int main(){    scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);    int u,v,c;    for(int i=1;i<=m;i++){        scanf("%d%d%d",&u,&v,&c);        g[u].push_back(P(v,c));        g[v].push_back(P(u,c));    }    dij(s);    int ans=inf;    for(int i=0;i<=k;i++)        ans=min(ans,d[t][i]);    printf("%d\n",ans);}