首页 > 代码库 > cogs 1111. 最短路

cogs 1111. 最短路

★   输入文件:shorta.in   输出文件:shorta.out   简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

给出N个点,M条无向边的简单图,问所有点对之间的最短路。

【输入格式】

第1行两个正整数N,M(N<=100,M<=5000)

下面M行,每行3个正整数x, y, w,为一条连接顶点x与y的边权值为w。(x<=n,y<=n,w<=1000)

【输出格式】

包括N行,每行N个数,第i行第j个数为点i到点j的最短路,第i行第i个数应为0,数字之间空格隔开。

【样例输入】

5 10
3 2 1
2 4 7
5 3 4
4 1 2
5 1 8
3 4 10
5 4 9
2 5 2
1 2 1
3 1 10

【样例输出】

0 1 2 2 3
1 0 1 3 2
2 1 0 4 3
2 3 4 0 5
3 2 3 5 0
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>

using namespace std;
const int N=110;
const int Maxn=99999999;

int a[N][N];

inline int read()
{
    int x=0;
    int f=1;
    char c=getchar();
    while(c<0||c>9){if(c==-)f=-1;c=getchar();}
    while(c>=0&&c<=9)x=x*10+c-0,c=getchar();
    return x*f;
}

int main()
{
    freopen("shorta.in","r",stdin);
    freopen("shorta.out","w",stdout);
    
    int n=read();
    int m=read();
    
    for(int i=1;i<=m;i++)
    {
        int u=read();
        int v=read();
        int w=read();
        if(u!=v)
            a[u][v]=a[v][u]=w;
    }
    
    for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
          {
              if(!a[i][j]&&i!=j)
                a[i][j]=Maxn;
            if(i==j)
                a[i][j]=0;
        }    
    
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    
    return 0;
}

 

cogs 1111. 最短路