bzoj2662: [BeiJing wc2012]冻结 最短路 建图

好久没有1A题啦♪(^∇^*)

一个sb建图，我居然调样例调了10min

看起来是双向边，其实在建图的时候要当成有向图，

否则他会时间倒流（233）

把每个点裂成k个点，然后把每条边裂成4条边（正向反向&膜不膜）

（话说我好像不会用openlivewriter贴代码，尴尬了）

 #include <bits/stdc++.h>

 #define poi(x,y) ((x)*(k+1)+(y))

 #define st poi(1,0)

 #define INF 2000000000

 using namespace std;

 int n,m,k,E;

 int from[],to[],nex[];

 int fir[],d[],w[];

 void add(int x,int y,int z)

 {

     from[++E]=x;to[E]=y;w[E]=z;nex[E]=fir[x];fir[x]=E;

 }

 int work()

 {

     for(int i=;i<=poi(n,k);i++)

         d[i]=INF;

     d[st]=;

     priority_queue<pair<int,int> > q;

     for(int i=fir[st];i;i=nex[i])

         q.push(make_pair(-w[i],i));

     while(!q.empty())

     {

         int tem=q.top().second;q.pop();

         if(to[tem]>=poi(n,))

             int e=;

         if(d[from[tem]]!=INF && d[from[tem]]+w[tem]<d[to[tem]])

         {

             d[to[tem]]=d[from[tem]]+w[tem];

             for(int i=fir[to[tem]];i;i=nex[i])

                 q.push(make_pair(-w[i],i));

         }

     }

     return d[poi(n,k)];

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&k);

     for(int i=;i<=m;i++)

     {

         int from,to,wei;

         scanf("%d%d%d",&from,&to,&wei);

         for(int j=;j<k;j++)

             add(poi(from,j),poi(to,j+),wei/),

             add(poi(to,j),poi(from,j+),wei/);

         for(int j=;j<=k;j++)

             add(poi(from,j),poi(to,j),wei),

             add(poi(to,j),poi(from,j),wei);

     }

     for(int i=;i<k;i++)

         add(poi(n,i),poi(n,k),);

     printf("%d\n",work());

     return ;

 }