Demo entry 6714214

Floyd-Warshall算法

   

Submitted by Cooper on Feb 12, 2018 at 13:36
Language: C++. Code size: 1.0 kB.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

int n, m, i, j, k, a, b, c;
int dist[110][110];
int main(int argc, char const *argv[]){
    while ((scanf("%d%d", &n, &m)) && (n != 0) && (m != 0)){
        memset(dist, 0x3f3f3f3f, sizeof(dist));
        for (int i = 1; i <= n; i++){
            dist[i][i] = 0;
        }
        for (int i = 1; i <= m; i++){
            scanf("%d%d%d", &a, &b, &c);
            dist[a][b] = c;
            dist[b][a] = c;
        }
        for (int k = 1; k <= n; k++){
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n; j++){
                    if (dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= n; ++j){
                printf("%d", dist[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).