最短路 (floyd)

本文主要是介绍最短路 (floyd)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<stdio.h>
#include<string.h>
#define min(a,b) (((a)<(b))?(a):(b))
#define inf 0x3f3f3f3f
int n,m;
int g[105][105];
void floyd() {
    for(int k=1;k<=n;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}
int main() {
    while(1) {
        memset(g,inf,sizeof(g));
        scanf("%d%d",&n,&m);
        if(n==0&&m==0) return 0;
        for(int i=0;i<m;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u][v]=w;
            g[v][u]=w;
        }
        floyd();
        printf("%d\n",g[1][n]);
    }
}

这篇关于最短路 (floyd)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！