BZOJ2069: [POI2004]ZAW

2069: [POI2004]ZAW

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 303 Solved: 138
[Submit][Status][Discuss]

Description

在
Byte山的山脚下有一个洞穴入口. 这个洞穴由复杂的洞室经过隧道连接构成. 洞穴的入口是一条笔直通向“前面洞口”的道路.
隧道互相都不交叉(他们只在洞室相遇). 两个洞室要么就通过隧道连接起来,要么就经过若干隧道间接的相连.
现在决定组织办一个'King's of Byteotia Cup' 比赛. 参赛者的目标就是任意选择一条路径进入洞穴并尽快出来即可.
一条路径必须经过除了“前面洞口”之外还至少要经过其他一个洞室.一条路径中一个洞不能重复经过(除了“前面洞室”以外),类似的一条隧道也不能重复经
过.
一个著名的洞穴探险家 Byteala 正准备参加这个比赛. Byteala 已经训练了数月而且他已获得了洞穴系统的一套详细资料.
对于每条隧道他都详细计算了从两个方向经过所需要的时间. 经过一个洞室的时间很短可以忽略不记. 现在Byteala 向计算一条符合条件的最优路径.

Input

第一行有两个数n 和 m (3 <= n <=
5000, 3 <= m <= 10000) 分别表示洞室的数目以及连接他们的隧道的数目. 洞室从1 到 n编号.
“前面洞室”的编号为1. 接下来m 行描述了所有的隧道. 每行四个整数a,b,c,d
表示从洞室a到洞室b需要c分钟的时间,而从洞室b到洞室a需要d分钟的时间, 1 <= a,b <= n, a <> b,
1 <= c,d <= 10000. 你可以假设符合要求的路径肯定存在.

Output

输出一行,最少需要多少时间完成比赛.

Sample Input

3 3
1 2 4 3
2 3 4 2
1 3 1 1

Sample Output

HINT

【题解】

http://blog.csdn.net/popoqqq/article/details/46458079

OrzPoPoQQQ

犯的傻逼错：

1、优先队列比较写反

2、A->B却没有B->A

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <queue>

 #include <vector>

 #define max(a, b) ((a) > (b) ? (a) : (b))

 #define min(a, b) ((a) < (b) ? (a) : (b))

 inline void read(long long &x)

 {

     x = ;char ch = getchar(), c = ch;

     while(ch < '' || ch > '')c = ch, ch = getchar();

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

     if(c == '-')x = -x;

 }

 const long long MAXN =  + ;

 const long long MAXM =  + ;

 const long long INF = 0x3f3f3f3f;

 struct Edge

 {

     long long u,v,w,next;

     Edge(long long _u, long long _v, long long _w, long long _next){u = _u;v = _v;w = _w;next = _next;}

     Edge(){}

 }edge[MAXM << ];

 long long head[MAXN],cnt;

 void insert(long long a, long long b, long long c)

 {

     edge[++cnt] = Edge(a,b,c,head[a]);

     head[a] = cnt;

 }

 long long n,m,to1[MAXN],from1[MAXN],node[MAXN],tot;

 long long A = , B = ;

 struct Node

 {

     long long v, d;

     Node(long long _v, long long _d){v = _v;d = _d;}

     Node(){}

 };

 struct cmp

 {

     bool operator()(Node a, Node b)

     {

         return a.d > b.d;

     }

 };

 std::priority_queue<Node, std::vector<Node>, cmp> q;

 long long d[MAXN], b[MAXN];

 void dijstra(long long s)

 {

     memset(b, , sizeof(b));

     memset(d, 0x3f, sizeof(d));

     while(q.size())q.pop();

     d[s] = ;

     q.push(Node(s, ));

     Node now;

     while(q.size())

     {

         now = q.top(), q.pop();

         if(now.d != d[now.v] || b[now.v])continue;

         b[now.v] = ;

         for(register long long pos = head[now.v];pos;pos = edge[pos].next)

         {

             long long v = edge[pos].v;

             if(v >  && v != A && v != B)continue;

             if(b[v])continue;

             if(d[now.v] + edge[pos].w < d[v])

             {

                 d[v] = d[now.v] + edge[pos].w;

                 q.push(Node(v, d[v]));

             }

         }

     }

 }

 long long ans = INF;

 int main()

 {

     read(n);read(m);

     register long long tmp1, tmp2, tmp3, tmp4;

     for(register long long i = ;i <= m;++ i)

     {

         read(tmp1), read(tmp2), read(tmp3), read(tmp4);

         if(tmp1 == )

         {

             node[++tot] = tmp2;

             to1[tot] = tmp4;

             from1[tot] = tmp3;

             continue;

         }

         else if(tmp2 == )

         {

             node[++tot] = tmp1;

             to1[tot] = tmp3;

             from1[tot] = tmp4;

             continue;

         }

         insert(tmp1, tmp2, tmp3);

         insert(tmp2, tmp1, tmp4);

     }

     long long M = ;

     while(( << M) <= n) ++ M;

     -- M;

     for(register long long i = ;i <= M;++ i)

     {

         for(register long long j = ;j <= tot;++ j)

         {

             if((node[j] >> i) & )

                 insert(A, node[j], from1[j]);

             else

                 insert(node[j], B, to1[j]);

         }

         dijstra(A);

         ans = min(ans, d[B]);

         A = B + ;

         B = B + ;

         for(register long long j = ;j <= tot;++ j)

         {

             if((node[j] >> i) & )

                 insert(node[j], A, to1[j]);

             else

                 insert(B, node[j], from1[j]);

         }

         dijstra(B);

         ans = min(ans, d[A]);

         A = B + ;

         B = B + ;

     }

     printf("%d", ans);

     return ;

 }

BZOJ2069