Description
来越多,因此选择最佳路径是很现实的问题。城市的道路是双向的,每条道路有固定的旅行时间以及需要支付的费用。路径由连续的道路组成。总时间是各条道路旅行时间的和,总费用是各条道路所支付费用的总和。同样的出发地和目的地,如果路径A比路径B所需时间少且费用低,那么我们说路径A比路径B好。对于某条路径,如果没有其他路径比它好,那么该路径被称为最优双调路径。这样的路径可能不止一条,或者说根本不存在。 给出城市交通网的描述信息,起始点和终点城市,求最优双条路径的条数。城市不超过100个,边数不超过300,每条边上的费用和时间都不超过100。
Input
第一行给出有多少个点,多少条边,开始点及结束点. 下面的数据用于描述这个地图
Output
有多少条最优双调路径
Sample Input
4 5 1 4
2 1 2 1
3 4 3 1
2 3 1 2
3 1 1 4
2 4 2 4
2 1 2 1
3 4 3 1
2 3 1 2
3 1 1 4
2 4 2 4
Sample Output
2
HINT
这道题的题面描述有些问题。
只要一条路没有其他路时间比他短并且花费比他少,那么它就是最优双调路径。
我们令dis[i][j]表示走到i点,话费了j元的最小时间(其实你也可以反过来,走到i点,花了j时间的最小话费)
可以得到dis[to][j+v[i]]=max(dis[to][j+v[i]],dis[i][j]+t[i]);
代码如下,细节比较少,很好写。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define INF 2139062143
#define MOD 10000007
#define LL long long
#define in(a) a=read()
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define DREP(i,k,n) for(int i=k;i>=n;i--)
#define cl(a) memset(a,0,sizeof(a))
inline int read(){
int x=,f=;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;
for(;isdigit(ch);ch=getchar()) x=x*+ch-'';
return x*f;
}
inline void out(int x){
if(x<) putchar('-'),x=-x;
if(x>) out(x/);
putchar(x%+'');
}
queue <pair<int,int> > Q;
int n,m,sta,des,ans=,minn=INF;
int dis[][*],vis[][*];
int total=,head[],to[],nxt[],t[],v[];
inline void adl(int a,int b,int c,int d){
total++;
to[total]=b;
v[total]=c;
t[total]=d;
nxt[total]=head[a];
head[a]=total;
return ;
}
inline void SPFA(int s){
memset(dis,,sizeof(dis));
dis[s][]=;
vis[s][]=;
Q.push(make_pair(s,));
while(!Q.empty()){
pair<int,int> k=Q.front();
Q.pop();
int u=k.first,w=k.second;
vis[u][w]=;
for(int e=head[u];e;e=nxt[e]){
int nw=w+v[e];
if(nw<= && dis[to[e]][nw]>dis[u][w]+t[e]){
dis[to[e]][nw]=dis[u][w]+t[e];
if(!vis[to[e]][nw]){
vis[to[e]][nw]=;
Q.push(make_pair(to[e],nw));
}
}
}
}
return ;
}
int main(){
int a,b,c,d;
in(n);in(m);in(sta);in(des);
REP(i,,m){
in(a);in(b);in(c);in(d);
adl(a,b,c,d);
adl(b,a,c,d);
}
SPFA(sta);
REP(i,,)
if(dis[des][i]<minn){
minn=dis[des][i];
ans++;
}
out(ans);
return ;
}