乘车路线「二维spfa」
题目描述
编号为 1∼N的 N 座城镇用若干仅供单向行驶的道路相连，每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）。BOB准备从城镇 1 出发到达城镇 N，但他目前只有 W 的钱，为此，你需要帮助他寻找一条从城镇 1 到城镇 N在他能支付的前提下的一条最短路线。
输入
W N M（N为城镇数目，2<=N<=100，M 为道路条数，1<=M<=10000,W 为钱的数目，0<=W<=1000）随后的 M行每行为一条道路的信息，包含 4 个数值（u,v,w,cost），表示从城镇 u 到 v 有一条长度为 w 的单向道路，经过这条道路需要花费 cost 。(1<=u,v<=N,1<=w<=100,0<=cost<=100)
输出
输出最短长度，若无解，则输出“NO ”；
样例输入
5 6 7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
样例输出
11
思路分析
- 乍一眼看去，最短路啊，再看一眼，诶？有问题，还多了一个限制条件就离谱
- 考试时直接按边权和钱数分别跑了两遍spfa，后来才发现正确性是不对的（
更离谱的是竟然水过了80分，最离谱的是有人暴搜AC了???）。 - 那么正确思路是什么？两个一起跑呗，一个二维spfa就彳亍，用到了一个本蒟蒻没用过的pair
详见代码
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 100+10,maxm = 1e4+10,inf = 0x3f3f3f3f;
int w,n,m;
int dis[maxn][1005],mon[maxn],ans[maxn],head[maxm],vis[maxn][1005];
struct edge{
int to,next,w,cost;
}e[maxm];
int len;
void addedge(int u,int v,int x,int y){
e[++len].to = v;
e[len].w = x;
e[len].cost = y;
e[len].next = head[u];
head[u] = len;
}
void spfa(int x){ //注意dis,vis都开二维
memset(dis,0x3f,sizeof(dis));
queue< pair<int,int> >q; //队列里存储的是pair
dis[x][0] = 0;
q.push(make_pair(x,0)); //用一个pair把dis和money一起压进去
while(!q.empty()){
pair<int,int> t = q.front();q.pop();
int u = t.first,money = t.second;
vis[u][money] = 0;
for(int i = head[u];~i;i = e[i].next){
int v = e[i].to;
if(money+e[i].cost>w)continue; //钱不够跑
if(dis[v][money+e[i].cost]>dis[u][money]+e[i].w){ //钱够跑并且可以松弛
dis[v][money+e[i].cost]=dis[u][money]+e[i].w;
if(!vis[v][money+e[i].cost]){
vis[v][money+e[i].cost] = 1;
q.push(make_pair(v,money+e[i].cost));
}
}
}
}
}
int main(){
scanf("%d%d%d",&w,&n,&m);
memset(head,-1,sizeof(head));
for(int i = 1;i <= m;i++){
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
addedge(a,b,c,d);
}
spfa(1);
int ans = inf;
for(int i = 0;i <= w;i++)ans = min(ans,dis[n][i]);
ans==inf ? printf("NO") : printf("%d",ans);
return 0;
}