原题如下:
试题 算法训练 最短路
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。
输入格式
第一行两个整数n, m。
接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。
输出格式
共n-1行,第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模与约定
对于10%的数据,n = 2,m = 2。
对于30%的数据,n <= 5,m <= 10。
对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。
思路分析
很多人看到这题之后认为不能使用dijstra算法,原因是题目中包含负权值,但其实这题也是可以使用dijistra算法的,因为题目中已经说明了,不包含负环,其实就是一个隐含条件,暗示我们可以使用dijkstra算法。
首先,简单介绍一下dijkstra算法不能计算负环的原因。
dijkstra算法本身是基于贪心算法的逻辑,每一次都基于现有路径条件计算到某一起点的最短值。但是负权值一旦出现,算法逻辑就不再成立了。
因为目的是得到最短路径,而在负环中,最短路径是负无穷大,从我们的常规认识上来说就已经出现了问题。
当然从算法角度上来说,真正的问题是,因为负环的出现,导致算法不能保证每一步找到的路径就是当前节点的最短路径,贪心算法的查找也就失去了意义。
所以这题,从条件上看好像可以使用djikstra算法。
但是,需要考虑到的是,djikstra的时间复杂度为(N^2),而节点的数量可以达到20000个。也就是说超时的可能性非常大,实际运行中也证实了我的猜想。
两个节点为20000的数据没能通过……
但是,你以为我在这里就结束了嘛?不?我不能止步于此。
我尝试性的小小删改了djikstra的贪心查找部分,结果很轻易的拿到了满分,这是我没想到的。因为从逻辑上来说,如果不基于贪心来查找的话,对付复杂的环状图是容易出现问题的。因为节点的确定的最短路径可能一直变化(贪心查找时确定之后是不变的)。
原因分析:可能是测试数据用的图不参杂环状图,或者是简单的环状图
下面是修改后的代码:
#include <iostream>
#include <stdio.h>
using namespace std;
int n, m,ma;
class l
{
public:
int v, d;
l *next;
void init (int a=-1, int b=0)
{
v = a;
d = b;
next = NULL;
}
};
l map [20005];
l* p;
class vertex
{
public:
int b;
int d;
vertex(int a=200000)
{
b = 0;
d = a;
}
};
vertex v[20005];
void shortestroute()
{
for (int i = 1; i < n; i++)
{
p = &map[0];
while (p != NULL)
{
if (p->v ==i)
{
v[i].d = p->d;
}
p = p->next;
}
}
ma = 200000;
for (int i = 1; i < n;)
{
for (int j = 1; j < n; j++)
{
if (v[j].b == 0 && v[j].d < ma)
{
i+=1;
v[j].b = 1;
p = &map[j];
while (p != NULL)
{
if (p->d + v[j].d < v[p->v].d)
{
v[p->v].d = p->d + v[j].d;
}
p = p->next;
}
}
}
}
for (int i = 1; i < n; i++)
{
cout << v[i].d<<endl;
}
}
int main()
{
int a,b,c;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &c);
if(map[a-1].d==0)
map[a-1].init(b-1, c);
else
{
p = new l;
p->init(b-1, c);
p->next = map[a-1].next;
map[a-1].next = p;
}
}
shortestroute();
return 0;
}