1 条题解

  • 0
    @ 2026-10-2 2:22:09

    用64位整数保存负边及大距离,单独的“-”表示无边。Floyd转移跳过不可达项,避免将无穷与负边相加,按顶点顺序输出不可达INF。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    
    int n,start;cin>>n>>start;const long long INF=LLONG_MAX/4;vector<vector<long long>>d(n,vector<long long>(n,INF));for(int i=0;i<n;i++)for(int j=0;j<n;j++){string s;cin>>s;if(s!="-")d[i][j]=stoll(s);}for(int k=0;k<n;k++)for(int i=0;i<n;i++)if(d[i][k]!=INF)for(int j=0;j<n;j++)if(d[k][j]!=INF)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);for(int i=0;i<n;i++)if(i!=start-1){cout<<"("<<start<<" -> "<<i+1<<") = ";if(d[start-1][i]==INF)cout<<"INF\n";else cout<<d[start-1][i]<<"\n";}
    
    return 0;
    }
    
    • 1

    信息

    ID
    4053
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者