Time Limit: 1 second
Memory Limit: 256 MB
问题描述
给出一个有向图G=(V,E)，和一个源点v0∈V，请写一个程序输出v0和图G中其他顶点的最短路径。只要所有的有向环都是正的，我们
就允许图的边有负值。顶点的标号从1到n（n为图G的顶点数）。
Input
第1行：一个正数n（2<=n<=80），表示图G的顶点总数。
第2行：一个整数，表示源点v0（V0∈V，V0可以是图G中任意一个顶点）。
第3至第n+2行，用一个邻接矩阵W给出了这个图。
Output
共包含n-1行，按照顶点编号从小到大的顺序，每行输出源点v0到一个顶点的最短距离。每行的具体格式参照样例。
Sample Input
5 1 0 2 - - 10 - 0 3 - 7 - - 0 4 - - - - 0 5 - - 6 - 0
Sample Output
(1->2)=2 (1->3)=5 (1->4)=9 (1->5)=9
【题解】
这题的数据超级坑的。。。他在每行的最后一个数字里面貌似会有多余的空格。。。。。、
说下思路。读取n行的字符串，整行读。
然后找到前n-1个空格。每个空格前面都是数字。然后再单独处理最后一个数字。。（有多余的空格要删掉）.
如果遇到的字符不是-，就在i上面加一个出度，并记录这个出度为j。然后记下权值w[i][j]。然后如果为-，则不理它就好。
最后用spfa解决问题就可以啦。
【代码】
#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;
int n,v0,a[100][100],team[200022];
long long w[100][100],dis[100];
bool exsit[100];
void input_data()
{
scanf("%d",&n);
scanf("%d",&v0);
getchar(); //用getline函数之前要先gechar用一下
for (int i = 1;i <= n;i++)
{
int p;
string ss;
getline(cin,ss); //整行读入ss字符串当中
for (int j = 1;j <= n-1;j++) //获取前n-1个空格的位置，这个位置前的字符皆为数字
{
p = ss.find(" ",0);
long long x;
bool flag = false;
for (int k = 0;k <= p-1;k++) //如果不全为'-'号，则说明这是一个数字
if (ss[k] != '-')
{
flag = true;
break;
}
if (flag && i!=j)
{
x = atoll(ss.c_str()); //atoll函数在stdlib.h当中，要记住这是c函数，里面是string.c_str()
a[i][0]++;
a[i][a[i][0]] = j; //增加i的一个出度，并记录这个出度是j
w[i][j] = x; //在i和j之间添加一条权值为x的边
}
ss = ss.erase(0,p+1); //删掉已经扫描过的数字
}
while ( ( p = ss.find(" ",0)) != -1) //“坑点” 要删掉多余的空格
ss = ss.erase(p,1);
bool flag = false;
for (int k = 0;k <= ss.size()-1;k++) //这是处理每行的最后一个数字 同上面的循环
if (ss[k]!='-')
{
flag = true;
break;
}
if (flag)
{
long long xx = atoll(ss.c_str());
a[i][0]++;
a[i][a[i][0]] = n;
w[i][n] = xx;
}
}
}
void spfa()
{
for (int i = 1;i <= n;i++)
dis[i] = 999999999999999; //一开始起点到除自身外所有点的距离皆为正无穷。。
dis[v0] = 0; //起点是0
int head = 0,tail = 1;
exsit[v0] = true;
team[1] = v0; //把起点加入队列 并标记已经存在于队列中
while (head != tail)
{
head++;
int f = team[head]; //取出头结点
exsit[f] = false;
for (int i = 1;i <= a[f][0];i++)//遍历它的出度 尝试更新最小值
{
int t = a[f][i];
if (dis[t] > dis[f] + w[f][t]) //如果能够更新最小值 就查看其是否在队列中，不在就加入队列
{
dis[t] = dis[f] + w[f][t];
if (!exsit[t])
{
exsit[t] = true;
tail++;
team[tail] = t;
}
}
}
}
}
void output_ans()
{
for (int i = 1;i <= n;i++) //最后输出不是起点的dis值
if (i != v0)
printf("(%d->%d)=%I64d
",v0,i,dis[i]);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
spfa();
output_ans();
return 0;
}