首页 > 代码库 > cogs 1111. 最短路
cogs 1111. 最短路
★ 输入文件:
时间限制:1 s 内存限制:128 MB
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. 最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。