第1行：一个正数n（2≤n≤80），表示图G的顶点总数。

第2行：一个整数，表示源点v0（v0∈V，v0可以是图G中任意一个顶点）。

第3至第n+2行，用一个邻接矩阵W给出了这个图。

共包含n-1行，按照顶点编号从小到大的顺序，每行输出源点v0到一个顶点的最短距离。每行的具体格式参照样例。

5
1
0 2 - - 10
- 0 3 - 7
- - 0 4 -
- - - 0 5
- - 6 - 0

(1 -> 2) = 2
(1 -> 3) = 5
(1 -> 4) = 9
(1 -> 5) = 9

样例所对应的图如下:

0. 题目概要

给定一个N个顶点的图（N<=80）和源点v0。图通过邻接矩阵给出，矩阵中包含整数权值（可能为负）和字符 -（表示无边）。要求计算源点到其他所有点的最短路径。

1. 核心思路

1.1 算法选择

虽然N很小，Floyd 或 Dijkstra 均可解。但考虑到题目含负权边且需处理单源最短路，SPFA 是一个性价比极高的选择。它既能处理负边，在稀疏图上的平均效率也优于 Bellman-Ford。

1.2 数据结构转化

• 输入：O(N^2)的邻接矩阵。

• 存储：为了优化 SPFA 的遍历效率，我们在读入时将矩阵转化为链式前向星（邻接表）。

• 转化逻辑：遍历矩阵 (i, j)，若内容不是 - 且不是 0（或根据题意忽略自环），则调用 addedge(i, j, w) 建边。

2. 重难点解析：字符串输入的“坑”

本题最大的难点在于输入数据的解析。

矩阵元素可能是：

1. 正整数（如 10）

2. 负整数（如 -5）

3. 无边标记（-）

难点：普通 cin >> int 会在读取到 - 字符时崩溃。必须使用 string 读取，然后分类讨论：

• 情况 A：正数

  • 判定：s[0] != '-'

  • 处理：遍历字符串，计算数值。

• 情况 B：无边

  • 判定：s[0] == '-' 且 s.size() == 1

  • 处理：跳过，不建边。

• 情况 C：负数

  • 判定：s[0] == '-' 且 s.size() > 1

  • 处理：从 s[1] 开始遍历计算数值，最后结果取反。

3. 易错点警示 

1. 负号与减号混淆：

   • 这是最容易 WA 的地方。必须严格区分代表“无边”的单个 - 和代表“负数”的 - 前缀。

   • 对策：使用 s.size() 辅助判断。

2. SPFA 的状态复位：

   • 出队时必须执行 is_used[u] = 0。这是 SPFA 与 Dijkstra 的本质区别（节点可能多次入队）。

3. 无穷大的输出控制：

   • 题目要求输出最短距离，如果不可达（dis[i]==0x3f3f3f3f）

4. 完整代码

#include <iostream>
#include <queue>
using namespace std;
int n,v0;
int h[100];
int dis[100];
int vtex[10000];
int nxt[10000];
int wt[10000];
int idx;
queue<int> q;
bool is_used[150];//标记每个点是否在队中

void spfa(int s){
    dis[s]=0;//源点到自己距离为0
    q.push(s);//源点入队
    is_used[s]=1;//标记源点已经入队
    while(!q.empty()){
        int tmp=q.front();//访问队首元素
        q.pop();//队首出队
        is_used[tmp]=0;//出队后解除标记
        int p=h[tmp];//tmp的头指针
        while(p!=-1){//访问所有p的邻接点
        //如果邻接点到源点的距离大于tmp到源点的距离+边权 就更新
            if(dis[vtex[p]]>dis[tmp]+wt[p]){
                dis[vtex[p]]=dis[tmp]+wt[p];
                //如果发生了更新且该邻接点不在队中就把邻接点入队
                if(is_used[vtex[p]]==0){
                    q.push(vtex[p]);
                    is_used[vtex[p]]=1;//并把邻接点打上标记
                }
            }
            p=nxt[p];//更新指针
        }   
    }
}

void addedge(int u,int v,int w){
    vtex[idx]=v;
    nxt[idx]=h[u];
    wt[idx]=w;
    h[u]=idx++;
}
int main(){
    cin>>n>>v0;
    string a;
    memset(h,-1,sizeof(h));//初始化邻接矩阵头指针数组
    //建图，将邻接矩阵变成邻接表
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int w=0;
            cin>>a;
            if(a[0]!='-'){//如果有边且为正边
                for(int k=0;k<a.size();k++){//字符串转换为数字
                    w=w*10+(a[k]-'0');
                }
                addedge(i,j,w);//有向图
            }
            //这里很容易出错，因为负数s[0]与没有边是一样的，所以很容易丢
            else if(a[0]=='-'&&a.size()!=1){//如果有边且为负边
                for(int k=1;k<a.size();k++){//字符串转换为数字
                    w=w*10+(a[k]-'0');
                }
                addedge(i,j,-w);//有向图 负边
            }
        }
    }
    /*//输出邻接表检查一下
    for(int i=1;i<=n;i++){
        cout<<i<<" :";
        int p=h[i];
        while(p!=-1){
            cout<<vtex[p]<<" "<<wt[p]<<" ";
            p=nxt[p];
        }
        cout<<endl;
    }
    */
    
    for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;//初始化dis数组为无穷
    spfa(v0);
    for(int i=1;i<=n;i++){//输出所有点到源点的距离
        //如果不是源点自身且有边存在
        if(i!=v0 && dis[i]!=0x3f3f3f3f)
            cout<<"("<<v0<<" -> "<<i<<")"<<" = "<<dis[i]<<endl;
    }
    
    return 0;
}