#include <bits/stdc++.h>
using namespace std;
int n,v0;
int m[105][105];
int dis[105];
int vis[105];
string s;
void dijks(int x){
    fill(dis,dis+n+1,999999);
    dis[x]=0;
    while(true){
        int k=0;
        for(int i=1;i<=n;i++)
            if(vis[i]!=true&&dis[i]<dis[k]) k=i;
        if(k==0) break;
        vis[k]=true;
        for(int i=1;i<=n;i++)
            if(m[k][i]==999999) continue;
            else if(vis[i]!=true&&dis[i]>dis[k]+m[k][i])
                dis[i]=dis[k]+m[k][i];
    }
}
int main(){
    cin>>n>>v0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>s;
            if(s!="-") m[i][j]=stoi(s);
            else m[i][j]=999999;
        }
    dijks(v0);
    for(int i=1;i<=n;i++)
        if(i==v0) continue;
        else printf("(%d -> %d) = %d\n",v0,i,dis[i]);
    return 0;
}
单源最短路dijkstra 不能处理负权边
dijkstra 每次找最短 贪心
多源最短路floyd 可以处理负权边，不能处理负权环
floyd
通过将所有点都当成中间点尝试一遍
1378
int main(){
    cin>>n>>v0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>s;
            if(s!="-") m[i][j]=stoi(s);
            else m[i][j]=999999;
        }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j||m[i][k]==999999||m[k][j]==999999) continue;
                if(m[i][j]>m[i][k]+m[k][j]){
                    m[i][j]=m[i][k]+m[k][j];
                }
            }
        }    
    }//时间复杂度O(n^3) 通常点数不超过1000可以使用
    for(int i=1;i<=n;i++)
        if(i==v0) continue;
        else printf("(%d -> %d) = %d\n",v0,i,dis[i]);
    return 0;
}