BZOJ2407/4398:探险/福慧双修(最短路)

Description

探险家小T好高兴&＃xff01;X国要举办一次溶洞探险比赛&＃xff0c;获奖者将得到丰厚奖品哦&＃xff01;小T虽然对奖品不感兴趣&＃xff0c;但是这个大振名声的机会当然不能错过&＃xff01;

比赛即将开始&＃xff0c;工作人员说明了这次比赛的规则&＃xff1a;每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路&＃xff0c;也有可能没有&＃xff0c;但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发&＃xff0c;并再次回到这个大溶洞。

如果就这么点限制&＃xff0c;那么问题就太简单了&＃xff0c;可是举办方又提出了一个条件&＃xff1a;不能经过同一条暗道两次。这个条件让大家犯难了。这该怎么办呢&＃xff1f;

到了大溶洞口后&＃xff0c;小T愉悦地发现这个地方他曾经来过&＃xff0c;他还记得有哪些暗道&＃xff0c;以及通过每条暗道的时间。小T现在向你求助&＃xff0c;你能帮他算出至少要多少时间才能回到大溶洞吗&＃xff1f;

Input

第一行两个数n&＃xff0c;m表示溶洞的数量以及暗道的数量。

接下来m行&＃xff0c;每行4个数s、t、w、v&＃xff0c;表示一个暗道连接的两个溶洞s、t&＃xff0c;这条暗道正着走&＃xff08;s à t&＃xff09;的所需要的时间w&＃xff0c;倒着走&＃xff08;t à s&＃xff09;所需要的时间v。由于溶洞的相对位置不同&＃xff0c;w与v可能不同。

Output

输出一行一个数t&＃xff0c;表示最少所需要的时间。

Sample Input

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

Sample Output

HINT

Solution

黄学长的博客讲的挺好的我就不赘述了……毕竟我抄的人家题解

不过黄学长的代码因为存的是前驱点好像有点萎……比如他博客下面那个数据就能叉掉好多人……

Code

1 #include
2 #include
3 #include
4 #include
5 #define N (1000009)
6 using namespace std;
7
8 struct Edge{int to,next,len;}edge[N];
9 struct Node
10 {
11 int num,dis;
12 bool operator <(const Node a) const {return dis>a.dis;}
13 };
14 int n,m,s[N],t[N],w[N],v[N],U,V,W,l,S&＃61;1,T&＃61;123456;
15 int head[N],num_edge,dis[N],pre[N],vis[N];
16 priority_queueq;
17
18 void add(int u,int v,int l)
19 {
20 edge[&＃43;&＃43;num_edge].to&＃61;v;
21 edge[num_edge].next&＃61;head[u];
22 edge[num_edge].len&＃61;l;
23 head[u]&＃61;num_edge;
24 }
25
26 int Low(int x){return min(x,((x-1)^1)&＃43;1);}
27
28 void Dijkstra()
29 {
30 memset(vis,false,sizeof(vis));
31 memset(dis,0x7f,sizeof(dis));
32 dis[1]&＃61;0; q.push((Node){1,0});
33 while (!q.empty())
34 {
35 Node x&＃61;q.top(); q.pop();
36 if (vis[x.num]) continue;
37 vis[x.num]&＃61;true;
38 for (int i&＃61;head[x.num]; i; i&＃61;edge[i].next)
39 if (dis[x.num]&＃43;edge[i].len<dis[edge[i].to])
40 {
41 dis[edge[i].to]&＃61;dis[x.num]&＃43;edge[i].len;
42 pre[edge[i].to]&＃61;(x.num&＃61;&＃61;1)?i:pre[x.num];
43 q.push((Node){edge[i].to,dis[edge[i].to]});
44 }
45 }
46 }
47
48 int main()
49 {
50 scanf("%d%d",&n,&m);
51 for (int i&＃61;1; i<&＃61;m; &＃43;&＃43;i)
52 {
53 scanf("%d%d%d%d",&s[i],&t[i],&w[i],&v[i]);
54 add(s[i],t[i],w[i]); add(t[i],s[i],v[i]);
55 }
56 Dijkstra();
57 memset(head,0,sizeof(head)); num_edge&＃61;0;
58 for (int i&＃61;1; i<&＃61;m; &＃43;&＃43;i)
59 for (int j&＃61;1; j<&＃61;2; &＃43;&＃43;j)
60 {
61 if (j&＃61;&＃61;1) U&＃61;s[i],V&＃61;t[i],W&＃61;w[i];
62 else U&＃61;t[i],V&＃61;s[i],W&＃61;v[i];
63 if (V&＃61;&＃61;1)
64 {
65 if (Low(pre[U])!&＃61;Low((i-1)*2&＃43;j)) add(S,T,dis[U]&＃43;W);
66 else add(U,T,W);
67 }
68 else if (U&＃61;&＃61;1)
69 {
70 if (Low(pre[V])!&＃61;Low((i-1)*2&＃43;j)) add(1,V,W);
71 }
72 else
73 {
74 if (pre[U]!&＃61;pre[V]) add(1,V,dis[U]&＃43;W);
75 else add(U,V,W);
76 }
77 }
78 Dijkstra();
79 printf("%d\n",dis[T]>2e9?-1:dis[T]);
80 }