题目描述
最短路径
思想
怎么想最短路其实根据三角形是最好想到的向下面的例子。
我们把更短的节点当做踏板来不停更新最小值即可找到终点的最小值。
最短路径中Dijkstra是最容易想到的算法,因为是贪心嘛所以很容易让人想到并且写出来。
当然这个也有坏处比如要是有负环的话就会出错。
个人代码
这里是用了优先队列来写因为这样会更快。
根据蓝书上面写的是不用优先队列来写的话复杂度是O(n^2),而使用了之后的话则是O(m log(n))。
因为单调队列默认的是优先大的所以设置了一个pair<>类型。
pair在排序中是按first来排序的所以第一个数据拿来存储最小值第二个拿来存储序号。
代码
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int sz=1e5+1;
int n,m,v[sz],h[sz],e[sz],nt[sz],ct,d[sz],f[sz];
void add(int x,int y,int z){v[++ct]=y,nt[ct]=h[x],e[ct]=z,h[x]=ct;}
int dj(int zx,int zy)
{
int i,x,y;for(i=1;i<=n;++i)d[i]=1e9;d[zx]=0;
priority_queue<pair<int,int> >q;q.push({0,zx});
while(q.size())
{
x=q.top().second;q.pop();
for(i=h[x];y=v[i],i;i=nt[i])
if(d[y]>d[x]+e[i])
{
d[y]=d[x]+e[i];q.push({-d[y],y});
}
}
return d[zy];
}
int main()
{
int i,x,y,z,s;
scanf("%d%d",&n,&m);
for(i=0;i<m;++i)scanf("%d%d%d",&x,&y,&z),add(x,y,z);
s=dj(1,n);
printf("%d",s==1e9?-1:s);
return 0;
}
这道题目的数据太水了!!!
最开始我的代码里q.push({-d[y],y};没有这个负号结果还是AC了!
等我把这个代码拿到下一道题目去提交才发现。。。。。