|
原题如下：
试题 算法训练 最短路
资源限制
时间限制：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;
}
|