8/4 floyd

Floyd

#include<bits/stdc++.h>
using namespace std;

int n,m,s,e;
bool vis[10005];
int INF=0x3f3f3f3f;
int d[1005][1005];
int p[1005][1005];
int G[1005][1005];

void floyd(){
    int i,j,k;
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            d[i][j]=G[i][j];
            if(d[i][j]<INF && i!=j){
                p[i][j]=i;
            }else {
                p[i][j]=-1;
            }
        }
    }
    for(k=1; k<=n; k++){
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++){
                if(d[i][k]+d[k][j]<d[i][j])    {
                    d[i][j]=d[i][k]+d[k][j];
                    p[i][j]=p[k][j];
                }
            }
        }
    }
}


int main(){
    memset(G,INF,sizeof(G));
    cin>>n>>m>>s>>e;
    for(int i=1; i<=m; i++){
        int xx,yy,zz;
        cin>>xx>>yy>>zz;
        G[xx][yy]=zz;
        G[yy][xx]=zz;
    }
    floyd();
    cout<<d[s][e]<<endl;
    return 0;
}