bzoj2292【POJ Challenge 】永远挑战*

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

bzoj2292【POJ Challenge 】永远挑战

题意：

有向图，每条边长度为1或2，求1到n最短路。点数≤100000，边数≤1000000。

题解：

有人说spfa会T，所以我用了dijkstra。不过这不是正解，神犇ZS告诉我正解应该是把所有边长度为2的边拆成两条，orz……

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 #define maxn 100010

 #define INF 0x3fffffff

 using namespace std;

 inline int read(){

     char ch=getchar(); int f=,x=;

     while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return f*x;

 }

 int n,m,d[maxn]; bool vis[maxn];

 struct e{int t,w,n;}; e es[maxn*]; int ess,g[maxn];

 void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}

 struct hn{int u,w; bool operator <(const hn &a)const{return w>a.w;}}; priority_queue<hn>q;

 int dijkstra(){

     inc(i,,n)d[i]=INF; d[]=; q.push((hn){,});

     while(!q.empty()){

         int x=q.top().u; while(!q.empty()&&vis[x])q.pop(),x=q.top().u; if(q.empty()&&vis[x])break;

         vis[x]=; for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){

             d[es[i].t]=d[x]+es[i].w; q.push((hn){es[i].t,d[es[i].t]});

         }

     }

     return d[n];

 }

 int main(){

     n=read(); m=read(); inc(i,,m){int a=read(),b=read(),c=read(); pe(a,b,c);}

     printf("%d",dijkstra()); return ;

 }