题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示1号点到n号点的最短距离。
如果路径不存在,则输出”impossible”。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过10000。
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm,该算法是西南交通大学段凡丁于1994年发表的(一看到这点就觉得西南交大碉堡了)。它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,其中k为所有顶点进队的平均次数,可以证明k一般小于等于2,可以处理负边,但无法处理带负环的图(负环和负边不是一个概念)。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单
——材料来源于网络
判断有无负环:如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)
C++ 代码
#include<cstdio>
#include<queue>
using namespace std;
const int N = 100000;
const int inf = 0x3f3f3f3f;
struct edge{ //邻接表
int to;
int next;
int dis;
}e[N << 1];
int head[N<< 1],dis[N << 1];
int cnt,n,m;
bool vis[N << 1];
void add(int u,int v,int d) //链式前向星 加边
{
e[++cnt].to = v;
e[cnt].dis = d;
e[cnt].next = head[u];
head[u] = cnt;
}
int spfa() //核心操作
{
queue<int>q;
dis[1]=0;
q.push(1);
vis[1]=true;
while(!q.empty())
{
int x = q.front();
q.pop();
vis[x]=false;
for(int i=head[x];i;i=e[i].next)
{
int y = e[i].to;
if(dis[y]>dis[x]+e[i].dis) //进行松弛
{
dis[y]=dis[x]+e[i].dis;
if(!vis[y])
{ q.push(y);
vis[y]=true;
}
}
}
}
return dis[n];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) dis[i]=inf; //初始化,更新为无穷大
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);//加入到邻接表中
}
if(spfa()==inf) puts("impossible"); //如果想到的那个点为无穷大,说明到不了;
else printf("%d",dis[n]);//否则输出
}