众所周知有一个东西叫做分层图。

众所又周知这道题数据不是很大。

所以直接 dp，dp[i][j] 表示时间为 i 时到 j 的最小花费。

然后你就能拿到 60 分。

因为一条路的时间可能为 0。

所以我们还得在每一层加一个最短路。

但是我加了非常多的优化，比如离散化和剪枝，所以尽量别模仿。

#include<bits/stdc++.h>
using namespace std;
const int N=110,inf=0x3f3f3f3f;
int dp[N*N*3][N],v[N*N*3],d[N],v1[N],mn[N];
#define PII pair<int,int>
vector<PII>G2[N];
void dij(int st)
{
	priority_queue<PII,vector<PII>,greater<PII> >q;
	memset(d,0x3f,sizeof(d));d[st]=0;
	memset(v1,0,sizeof(v1));
	q.push({0,st});
	while(!q.empty())
	{
		int x=q.top().second;q.pop();
		if(v1[x])continue;v1[x]=1;
		for(auto i:G2[x])
		{
			int y=i.first,w=i.second;
			if(d[y]>d[x]+w)d[y]=d[x]+w,q.push({d[y],y});
		}
	}
}
struct node{int x,c,t;};vector<node>G[N];
signed main()
{
	int n,m,st,ed;cin>>n>>m>>st>>ed;
	for(int i=1;i<=m;i++)
	{
		int x,y,c1,c2;cin>>x>>y>>c1>>c2;
		G[x].push_back({y,c1,c2});
		G[y].push_back({x,c1,c2});
	}
	memset(dp,0x3f,sizeof(dp));dp[0][st]=0;
	memset(mn,0x3f,sizeof(mn));
	priority_queue<int,vector<int>,greater<int>>q;q.push(0);v[0]=1;int mx=0;
	while(!q.empty())
	{
		int x=q.top();q.pop();mx=max(mx,x);
		memset(G2,0,sizeof(G2));
		for(int i=1;i<=n;i++)G2[0].push_back({i,dp[x][i]});
		for(int i=1;i<=n;i++)
		{
			for(auto j:G[i])if(j.t==0)
				G2[i].push_back({j.x,j.c});
		}
		dij(0);
		for(int i=1;i<=n;i++)dp[x][i]=d[i];
		for(int i=1;i<=n;i++)if(dp[x][i]!=inf)
		{
			if(dp[x][i]>=mn[i])continue;mn[i]=dp[x][i];
			for(auto j:G[i])if(j.t!=0)
			{
				int y=j.x,c=j.c,t=j.t;
				dp[x+t][y]=min(dp[x+t][y],dp[x][i]+c);
				if(!v[x+t])q.push(x+t);v[x+t]=1;
			}
		}
	}
	int pos=inf,ans=0;
	for(int i=0;i<=mx;i++)if(dp[i][ed]<pos)pos=dp[i][ed],ans++;
	cout<<ans;
	return 0;
}

题目描述

题目大意

在一张无向图中，我们给出一些边，这一条边有我们对应需要的通过这条边的时间和花费，从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;//结束程序
}