1 条题解

  • 0
    @ 2026-10-2 2:21:43

    用 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
    上传者