Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
150126 | I am BM | 最短路径 | C++ | 通过 | 100 | 0 MS | 260 KB | 634 | 2024-06-01 15:46:27 |
#include<bits/stdc++.h> using namespace std; const int maxi=0x7ffff; int f[105][105],w[101][101]; int N,a,b,c; int main() { cin>>N; for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { w[i][j]=maxi; } } cin>>a>>b>>c; while (a!=0&&b!=0&&c!=0) { w[a][b]=c; cin>>a>>b>>c; } for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { f[i][j]=w[i][j]; } } for (int k=1;k<=N;k++) { for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { if ((i!=j)&&(i!=k)&&(j!=k)&&(f[i][k]+f[k][j]<f[i][j])) f[i][j]=f[i][k]+f[k][j]; } } } cout<<f[1][N]; return 0; }