1 条题解
-
0
用 Dijkstra 计算通用正权有向图最短路,允许回边,避免旧题解只处理编号递增边而漏掉更短路径。
#include <bits/stdc++.h> using namespace std; int main(){int n;cin>>n;vector<vector<long long>>a(n,vector<long long>(n));for(auto&r:a)for(auto&x:r)cin>>x;const long long INF=LLONG_MAX/4;vector<long long>d(n,INF);vector<int>p(n,-1),seen(n);d[0]=0;for(int turn=0;turn<n;turn++){int u=-1;for(int i=0;i<n;i++)if(!seen[i]&&(u<0||d[i]<d[u]))u=i;if(u<0||d[u]==INF)break;seen[u]=1;for(int v=0;v<n;v++)if(a[u][v]>0&&d[u]+a[u][v]<d[v]){d[v]=d[u]+a[u][v];p[v]=u;}}vector<int>path;for(int u=n-1;u>=0;u=p[u])path.push_back(u+1);reverse(path.begin(),path.end());cout<<"minlong="<<d[n-1]<<"\n";for(int u:path)cout<<u<<' ';cout<<"\n";}
- 1
信息
- ID
- 3936
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者