Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
150179 | I am BM | 最小交通费用问题 | C++ | 通过 | 100 | 3 MS | 368 KB | 907 | 2024-06-01 16:16:16 |
#include<bits/stdc++.h> using namespace std; const int maxi=0x7ffff; int f[105][105],w[101][101],f1[105][105]; int N,a,b,c,M,start,stop; int main() { cin>>N>>M; for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { w[i][j]=maxi; } } for (int i=1;i<=M;i++) { cin>>a>>b>>c; w[a][b]=c; } cin>>start>>stop; for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { f1[i][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]; } } } for (int k=N;k>=1;k--) { for (int i=N;i>=1;i--) { for (int j=N;j>=1;j--) { if ((i!=j)&&(i!=k)&&(j!=k)&&(f1[i][k]+f1[k][j]<f1[i][j])) f1[i][j]=f1[i][k]+f1[k][j]; } } } cout<<f[start][stop]+f1[stop][start]; return 0; }