【拆点+最短路】双调路径

图论

传送门：CodeVS1240

2002年BOI巴尔干半岛信息学奥赛（还有这种比赛？）

思路比较清晰，由于每条边都有两个权，一起弄肯定不行啊，所以就拆点（另有一说是分层）

随便取一个权值拆点，例如把城市i拆成花j个费用到城市j，

然后跑最短路，

最后统计一下。

注意：相同两个城市可能有连边（没毛病）！

代码如下（dijkstra）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 3000000
int tot,n,m,s,t,x,y,xx,yy,ans;
int head[80000],dist[80000],cost[80000],nxt[80000],v[80000],dis[300][30000];
bool flag,vis[300][30000];
struct route{
	int x,y,d;	
	bool operator > (const route n) const {return d>n.d;}
};
priority_queue< route,vector<route>,greater<route> > h;
void add(int x,int y,int xx,int yy){
	tot++; v[tot]=y; dist[tot]=xx; cost[tot]=yy; nxt[tot]=head[x];
	head[x]=tot;
}
void dijkstra(int s,int t){
	for (int i=1;i<=n;i++)
		for (int j=0;j<=10000;j++)
			dis[i][j]=INF;
	h.push((route){s,0,0});
	dis[s][0]=0;
		
	while (!h.empty()){
		int x=h.top().x,y=h.top().y,d=h.top().d;
		h.pop();
		for (int j=head[x];j;j=nxt[j])
			if (dis[v[j]][y+cost[j]]>d+dist[j]){
				dis[v[j]][y+cost[j]]=d+dist[j];
				h.push((route){v[j],y+cost[j],dis[v[j]][y+cost[j]]});
			}
	}
	
	return;
}
				
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d%d",&x,&y,&xx,&yy);
		add(x,y,xx,yy); add(y,x,xx,yy);
	}
	
	dijkstra(s,t);
	
	int MIN=INF;
	for (int i=0;i<=10000;i++)
		if (dis[t][i]<MIN){ans++; MIN=dis[t][i];}
	
	printf("%d\n",ans);
	
	return 0;
}