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

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <queue>
  6 #include <vector> 
  7 #define max(a, b) ((a) > (b) ? (a) : (b))
  8 #define min(a, b) ((a) < (b) ? (a) : (b))
  9 
 10 inline void read(long long &x)
 11 {
 12     x = 0;char ch = getchar(), c = ch;
 13     while(ch < '0' || ch > '9')c = ch, ch = getchar();
 14     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
 15     if(c == '-')x = -x;
 16 }
 17 
 18 const long long MAXN = 50000 + 100;
 19 const long long MAXM = 100000 + 100;
 20 const long long INF = 0x3f3f3f3f;
 21 
 22 struct Edge
 23 {
 24     long long u,v,w,next;
 25     Edge(long long _u, long long _v, long long _w, long long _next){u = _u;v = _v;w = _w;next = _next;}
 26     Edge(){}
 27 }edge[MAXM << 1];
 28 long long head[MAXN],cnt;
 29 
 30 void insert(long long a, long long b, long long c)
 31 {
 32     edge[++cnt] = Edge(a,b,c,head[a]);
 33     head[a] = cnt;
 34 }
 35 
 36 long long n,m,to1[MAXN],from1[MAXN],node[MAXN],tot;
 37 
 38 long long A = 6000, B = 6001;
 39 
 40 struct Node
 41 {
 42     long long v, d;
 43     Node(long long _v, long long _d){v = _v;d = _d;}
 44     Node(){}
 45 };
 46 
 47 struct cmp
 48 {
 49     bool operator()(Node a, Node b)
 50     {
 51         return a.d > b.d;
 52     }
 53 };
 54 
 55 std::priority_queue<Node, std::vector<Node>, cmp> q;
 56 
 57 long long d[MAXN], b[MAXN];
 58 
 59 void dijstra(long long s)
 60 {
 61     memset(b, 0, sizeof(b));
 62     memset(d, 0x3f, sizeof(d));
 63     while(q.size())q.pop();
 64     d[s] = 0;
 65     q.push(Node(s, 0));
 66     Node now;
 67     while(q.size())
 68     {
 69         now = q.top(), q.pop();
 70         if(now.d != d[now.v] || b[now.v])continue;
 71         b[now.v] = 1;
 72         for(register long long pos = head[now.v];pos;pos = edge[pos].next)
 73         {
 74             long long v = edge[pos].v;
 75             if(v > 6000 && v != A && v != B)continue;
 76             if(b[v])continue;
 77             if(d[now.v] + edge[pos].w < d[v])
 78             {
 79                 d[v] = d[now.v] + edge[pos].w;
 80                 q.push(Node(v, d[v])); 
 81             }
 82         }
 83     }
 84 }
 85 
 86 long long ans = INF;
 87 
 88 int main()
 89 {
 90     read(n);read(m);
 91     register long long tmp1, tmp2, tmp3, tmp4;
 92     for(register long long i = 1;i <= m;++ i)
 93     {
 94         read(tmp1), read(tmp2), read(tmp3), read(tmp4);
 95         if(tmp1 == 1)
 96         {
 97             node[++tot] = tmp2;
 98             to1[tot] = tmp4;
 99             from1[tot] = tmp3;
100             continue;
101         }
102         else if(tmp2 == 1)
103         {
104             node[++tot] = tmp1;
105             to1[tot] = tmp3;
106             from1[tot] = tmp4;
107             continue;
108         }
109         insert(tmp1, tmp2, tmp3);
110         insert(tmp2, tmp1, tmp4);
111     }
112     long long M = 0;
113     while((1 << M) <= n) ++ M;
114     -- M;
115     for(register long long i = 0;i <= M;++ i)
116     {
117         for(register long long j = 1;j <= tot;++ j)
118         {
119             if((node[j] >> i) & 1)
120                 insert(A, node[j], from1[j]);
121             else
122                 insert(node[j], B, to1[j]);
123         } 
124         dijstra(A);
125         ans = min(ans, d[B]);
126         A = B + 1;
127         B = B + 2;
128         for(register long long j = 1;j <= tot;++ j)
129         {
130             if((node[j] >> i) & 1)
131                 insert(node[j], A, to1[j]);
132             else
133                 insert(B, node[j], from1[j]);
134         }
135         dijstra(B);
136         ans = min(ans, d[A]);
137         A = B + 1;
138         B = B + 2;
139     } 
140     printf("%d", ans);
141     return 0;
142 }

BZOJ2069