Floyd AcWing 854. Floyd finds the shortest path

Floyd AcWing 854. Floyd Find the shortest path

Original link

AcWing 854. Floyd Find the shortest path

Algorithm tags

shortest path Floyd

Ideas

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 205, INF = 0x3f3f3f3f;
int d[N][N];
int n,m,k;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void fl(){
    rep(k, 1, n+1){
        rep(i, 1, n+1){
            rep(j, 1, n+1){
                d[i][j]=min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n=read(), m=read(), k=read();
    rep(i, 1, n+1){
        rep(j, 1, n+1){
            if(i-j){
                d[i][j]=INF;
            }else{
                d[i][j]=0;
            }
        }
    }
    while(m--){
        int x=read(), y=read(), z=read();
        d[x][y]=min(d[x][y], z);
    }
    fl();
    while(k--){
        int x=read(), y=read();
        if(d[x][y]>INF/2){
            puts("impossible");
        }else{
            printf("%lld\n", d[x][y]);
        }
    }
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support