题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。
输入格式:
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。
输出格式:
输出一个整数,表示 1 号点到 n 号点的最短距离。
如果路径不存在,则输出 −1。
数据范围:
1≤n,m≤1.5×105,
图中涉及边长均不小于 0,且不超过 10000。
数据保证:如果最短路存在,则最短路的长度不超过 109。
样例
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
算法1
(Dijkstra) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=150010;
typedef pair<int,int> PII;
//临接表
int e[N],ne[N],h[N],w[N],idx;
//dist[]记录距离,st[]记录是否遍历过
int n,m,dist[N],st[N];
void add(int a,int b,int c)//构造链表
{
w[idx]=c;
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int Dijkstra()
{
memset(dist,0x3f,sizeof dist);//初始化
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;//构造小根堆
heap.push({0,1});//存入根节点
while(!heap.empty())
{
auto item=heap.top();
heap.pop();
int ver=item.second,distance=item.first;
if(st[ver]) continue;
st[ver]=1;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>distance+w[i])
{
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);//初始化
while(m--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
cout<<Dijkstra()<<endl;
return 0;
}
/*错点:1、
总结反思:1、构造小根堆
2、 权重:w[idx]=c,不用担心w[i]的值是一样的
3、一直在想用队列可不可以,在大佬这层搞明白了,不可以的。
如果用队列的话,当出现一个点二次进队的情况时(既然能二次进队,就证明第二次更新的距离更短),
如果此时不用st数组来表明状态的话,那么就有重复性工作(即同一个点距离长的跟更新了一遍,
距离短的又跟新了一遍)此时可能思路正确,但是会超时,如果用st数组来表明状态的话,
那么第二次进队的那个距离短的情况就不能去更更新了。*/
算法2
(用队列的错误示范) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6;
int h[N],e[N],ne[N],w[N],idx;
int n,m,d[N],q[N];
void add(int a,int b,int s)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=s;
h[a]=idx++;
}
int bfs()
{
memset(d,0x3f3f3f3f,sizeof d);
int hh=0,tt=-1;
d[1]=0;
q[++tt]=1;
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(d[j]>d[t]+w[i])
{
cout<<"d["<<j<<"]"<<"="<<d[t]<<"+"<<w[i]<<endl;
d[j]=d[t]+w[i];
q[++tt]=j;
}
}
}
if(d[n]==0x3f3f3f3f) return -1;
else return d[n];
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
int a,b,s;
while(m--)
{
scanf("%d%d%d",&a,&b,&s);
add(a,b,s);
}
printf("%d",bfs());
return 0;
}