当前位置: 代码迷 >> 综合 >> BZOJ 2407 探险
  详细解决方案

BZOJ 2407 探险

热度:29   发布时间:2024-01-19 01:58:27.0

Description

探险家小T好高兴!X国要举办一次溶洞探险比赛,获奖者将得到丰厚奖品哦!小T虽然对奖品不感兴趣,但是这个大振名声的机会当然不能错过!
比赛即将开始,工作人员说明了这次比赛的规则:每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路,也有可能没有,但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发,并再次回到这个大溶洞。
如果就这么点限制,那么问题就太简单了,可是举办方又提出了一个条件: 不能经过同一条暗道两次。这个条件让大家犯难了。这该怎么办呢?
到了大溶洞口后,小T愉悦地发现这个地方他曾经来过,他还记得有哪些暗道,以及通过每条暗道的时间。小T现在向你求助,你能帮他算出至少要多少时间才能回到大溶洞吗?

Input

第一行两个数n,m表示溶洞的数量以及暗道的数量。

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

Output

输出一行一个数t,表示最少所需要的时间。

Sample Input

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

Sample Output

8

HINT

N<=10000,M<=200000,1<=W,V<=10000

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

dijkstra+思路~

单独处理从1出发后,就可以用最短路来做了。

每个点记录从1到它的最短两条路以及它走的路径是从与1相连的哪条边来的,然后dijkstra即可。

bool operator里面是>啊啊啊啊!


#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;int n,m,x,y,s,t,fi[10001],w[400001],ne[400001],v[400001],cnt,d1[10001],d2[10001];
int f1[10001],f2[10001],len[10001];struct node{int w,f,dis;
};bool operator < (node u,node v)
{return u.dis>v.dis;
}int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; 
}void add(int u,int vv,int val1,int val2)
{w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val1;w[++cnt]=u;ne[cnt]=fi[vv];fi[vv]=cnt;v[cnt]=val2;
}int cal()
{priority_queue<node> q;memset(d1,0x3f,sizeof(d1));memset(d2,0x3f,sizeof(d2));int k,f,dis;for(int i=fi[1];i;i=ne[i]){f=i>>1;if(d1[w[i]]>v[i]){if(f1[w[i]]!=f) f2[w[i]]=f1[w[i]],d2[w[i]]=d1[w[i]];f1[w[i]]=f;d1[w[i]]=v[i];}else if(f!=f1[w[i]] && d2[w[i]]>v[i]) f2[w[i]]=f,d2[w[i]]=v[i];else continue;q.push((node){w[i],f,v[i]});}while(!q.empty()){f=q.top().f;k=q.top().w;dis=q.top().dis;q.pop();if(!(f==f1[k] && d1[k]==dis) && !(f==f2[k] && d2[k]==dis)) continue;for(int i=fi[k];i;i=ne[i])if((i>>1)!=f){if(d1[w[i]]>v[i]+dis){if(f1[w[i]]!=f) f2[w[i]]=f1[w[i]],d2[w[i]]=d1[w[i]];f1[w[i]]=f;d1[w[i]]=v[i]+dis;}else if(f!=f1[w[i]] && d2[w[i]]>v[i]+dis) f2[w[i]]=f,d2[w[i]]=v[i]+dis;else continue;q.push((node){w[i],f,v[i]+dis});}}return d1[1];
}int main()
{n=read();m=read();cnt=1;for(int i=1;i<=m;i++) x=read(),y=read(),s=read(),t=read(),add(x,y,s,t);printf("%d\n",cal());return 0;
}