Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
151056 | 吴宗桦 | 最短路径 | C++ | 通过 | 100 | 0 MS | 268 KB | 765 | 2024-06-11 13:59:44 |
#include<iostream> using namespace std; int a,b,c,d,e[114][114],f[105][105],g[114],h[114],i[114],j,k,l,m,n; int main() { cin>>a;//a结点个数 b边的条数 g[1]=1; g[0]=1; while(g[b]!=0) { b++; cin>>g[b]>>h[b]>>i[b]; } for(c=1;c<=a;c++) { for(d=1;d<=b;d++) { e[c][d]=999999999; e[c][c]=0; f[c][c]=c; } } for(c=1;c<=b;c++) { e[g[c]][h[c]]=i[c]; f[g[c]][h[c]]=g[c]; } for(c=1;c<=a;c++) { for(d=1;d<=a;d++) { for(j=1;j<=a;j++) { if(e[d][c]+e[c][j]<e[d][j]) { e[d][j]=e[d][c]+e[c][j]; f[d][j]=f[c][j]; } } } } cout<<e[1][a]<<endl; //for(c=1;c<=a;c++) //{ //for(d=1;d<=a;d++) //cout<<e[c][d]<<" "; //cout<<endl; //} return 0; }