题意：

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

题解：

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

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 #define INF 0x3fffffff 8 using namespace std; 9 10 inline int read(){11     char ch=getchar(); int f=1,x=0;12     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();14     return f*x;15 }16 int n,m,d[maxn]; bool vis[maxn];17 struct e{
   int t,w,n;}; e es[maxn*10]; int ess,g[maxn];18 void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}19 struct hn{
   int u,w; bool operator <(const hn &a)const{
   return w>a.w;}}; priority_queue
         
          q;20 int dijkstra(){21     inc(i,1,n)d[i]=INF; d[1]=0; q.push((hn){
   1,0});22     while(!q.empty()){23         int x=q.top().u; while(!q.empty()&&vis[x])q.pop(),x=q.top().u; if(q.empty()&&vis[x])break;24         vis[x]=1; for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){25             d[es[i].t]=d[x]+es[i].w; q.push((hn){es[i].t,d[es[i].t]});26         }27     }28     return d[n];29 }30 int main(){31     n=read(); m=read(); inc(i,1,m){
   int a=read(),b=read(),c=read(); pe(a,b,c);}32     printf("%d",dijkstra()); return 0;33 }
         
        
       
      
     

 

20160905