Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
153472 | 陈家宝 | 最短路径 | C++ | 通过 | 100 | 0 MS | 336 KB | 920 | 2024-07-03 13:21:06 |
#include<bits/stdc++.h> using namespace std; vector<int> vec; int n,o=-1,t=-1,th=-1,a[101][101],f[5000],indegree[5000]; void TopSort(int a[101][101],int *indegree){ queue<int> q; while(!q.empty()||vec.size()<n){ for(int i=1;i<=n;i++) if(indegree[i]==0){ q.push(i); indegree[i]=-1; } int v=q.front(); vec.push_back(v); q.pop(); for(int i=1;i<=n;i++)if(a[v][i]!=-1&&indegree[i]!=-1)indegree[i]--; } } int main(){ scanf("%d",&n); memset(f,127,sizeof(f)); memset(indegree,0,sizeof(indegree)); memset(a,-1,sizeof(a)); while(o!=0&&t!=0&&th!=0){ cin>>o>>t>>th; a[o][t]=th; indegree[t]++; } TopSort(a,indegree); f[n]=0; for(int i=n-2;i>=0;i--) for(int j=n-1;j>i;j--){ int I=vec[i],J=vec[j]; if(a[I][J]>0&&f[J]!=0x7f7f7f7f)f[I]=min(f[I],f[J]+a[I][J]); } printf("%d",f[1]); return 0; }