Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
150234 | 陈馨逸 | 最短路径 | C++ | 通过 | 100 | 0 MS | 324 KB | 625 | 2024-06-01 16:41:04 |
#include<bits/stdc++.h> using namespace std; const int BM=133; int n,f[BM][BM],a,b,c,dis[BM]; bool v[BM]; int main() { for(int i=0;i<BM;i++)//初始化 { for(int j=0;j<BM;j++) { f[i][j]=1e9; } dis[i]=1e9; f[i][i]=0; } dis[1]=0; cin>>n; while(cin>>a>>b>>c&&(a!=0||b!=0||c!=0)) { f[a][b]=c; } int d=-1,e=1e9; while(true) { d=-1,e=1e9; for(int i=1;i<=n;i++) { if(dis[i]<e&&!v[i]) { d=i; e=dis[i]; } } if(d==-1)break; v[d]=true; for(int i=1;i<=n;i++) { if(!v[i])dis[i]=min(dis[i],dis[d]+f[d][i]); } } cout<<dis[n]; }