[文章目录]
Description
N个点，M条边的有向图，求点1到点N的最短路（保证存在）。1<=N<=1000000，1<=M<=10000000
配对堆优化dijkstra。【STL】
这个堆可以直接修改，真好啊。。。【话说建图的时候前面那些好像都是没有用的边啊。。。】
估计过段时间就忘了咋写了，没事可以复习复习。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
struct node
{
int x,dis;
};
bool operator < (const node &x,const node &y)
{
return x.dis>y.dis;
}
__gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag>q;
__gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag>::point_iterator h[1001000];
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char ch=nc(),f=0;
while(!isdigit(ch)){if(ch=='-') f=1; ch=nc();}
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
if(f) x=-x;
}
struct edge
{
int to,nxt,data;
}ed[10001000];
int head[1001000],cnt,n;
inline void add(int x,int y,int z)
{
ed[++cnt].to=y; ed[cnt].data=z;
ed[cnt].nxt=head[x]; head[x]=cnt;
}
ll dis[1001000];
inline ll dijkstra()
{
memset(dis,0x3f,(sizeof(ll))*(n+10));
dis[1]=0; h[1]=q.push((node){1,0}); int x,y;
while(!q.empty())
{
x=q.top().x; q.pop();
if(x==n) return dis[n];
for(int i=head[x];i;i=ed[i].nxt) if(dis[y=ed[i].to]>dis[x]+ed[i].data)
{
dis[y]=dis[x]+ed[i].data;
if(h[y]!=0) q.modify(h[y],(node){y,dis[y]});
else h[y]=q.push((node){y,dis[y]});
}
}
return -1;
}
int main()
{
read(n); int m,t,x,y,z; read(m); read(t); m-=t;
read(t); read(t); read(t); read(t); read(t);
while(m--)
{
read(x); read(y); read(z);
add(x,y,z);
}
printf("%lld",dijkstra());
return 0;
}