自动搬运

查看原文

来自洛谷，原作者为

	哲学家 CSP-S 2020 加油！

搬运于2025-08-24 22:11:43，当前版本为作者最后更新于2020-07-27 20:45:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

题目大意

在一张无向图中，我们给出一些边，这一条边有我们对应需要的通过这条边的时间和花费，从A点到B点可能有N多种方式到达，对于每种方式当我们的花费和时间都比其中一种方式大时，此种方式不是最短路，但是如果一种方式花费小而时间大，一种方式时间大而花费小，这样我们无法比较，两种方式都暂时属于我们的最短路。

题目分析

本题的题目要求求出从 s 到 e 的最小路径条数

在我们理解了题意之后，应该是很容易就能想出双限制的最短路做法（把我们的dis值用一个二维数组来表示）

普通最短路就是距离限制，我们通过 dis[x] 表示到达点 x 的最小距离

本题最短路则是限制距离（时间）和花费，那我们就加一维使其变成二维数组，那么我们的dis就会有两个值来控制。

—— 用 dis[x][y] 表示到达点 x 花费 y 块钱的最小距离（时间）

最后枚举花费 i ，然后找到满足最短路径的点 dis[e][i]，有多少这样的点我们就可以用一个累加器ans来累计答案，最后输出就行了

怎么判断是否是满足最短路径的点？

设一个变量 last（我用的是last，自己可以随便定义） == 0x3f3f3f3f（极大值就可以） ，如果当前的 dis[e][i] <ans ，则是满足我们条件的点（ ans 表示的是时间）

代码

#include <bits/stdc++.h>//万能头文件
using namespace std;
int n,m,st,ed;
struct edge{结构体
	int v;
	int w;
	int t;
};
vector<edge> e[105];//结构体数组e中有 i v w t四个数表示从i点到v点的距离为w，时间为t
int d[105][100005];//这个d数组第一维是表示第几种方式第二维表示时间值表示金钱（花费）
bool vis[105];//记录是否重复判断
int main() {
	memset(vis,0,sizeof(vis));
	memset(d,127,sizeof(d));//“127”代表的是一个极大的值
	cin>>n>>m>>st>>ed;
	for(int i=1;i<=m;i++){
		int u,v,w,t;
		cin>>u>>v>>w>>t;
		e[u].push_back((edge){v,w,t});
		e[v].push_back((edge){u,w,t});
	}//预处理
	queue<int> q;
	q.push(st);
	vis[st]=1;
	for(int i=1;i<=10000;i++)d[st][i]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].v,w=e[u][i].w,t=e[u][i].t;
			bool flag=0;
			for(int j=0;j<=10000-w;j++){
				if(d[v][j+w]>d[u][j]+t){
					d[v][j+w]=d[u][j]+t;
					flag=1;
				}
			}
			if(flag){
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}//spfa的模板
	int ans=0,last=99999999;
	/*
	for(int i=1;i<=n;i++){
		for(int j=1;j<=15;j++){
			cout<<d[i][j]<<' ';
		}
		cout<<endl;
	}
	*/ //当时调试用的，不影响
	for(int i=0;i<=10000;i++){
		if(d[ed][i]>=last)continue;
		last=d[ed][i];
		ans++;//ans累加，输出答案
	}
	cout<<ans;
	return 0;//结束程序
}