题面

【问题描述】

由于 A 学校生物实验室里那个不负责的数据分析员，实验室的病毒威力被错误估算，导致了可怕的病毒泄漏，现在病毒即将在校园内传播开来。

校园里一共有 n 个建筑物，生物实验室总是位于一号建筑物且在 0 时刻受到病毒入侵。这 n 个建筑物由 m 条单向道路相连（也有可能有建筑物被孤立）。每条道路有两个信息：它的长度，它是多少年前修建的。当一个建筑物被病毒入侵，从被入侵的时刻起，病毒会从所有由这个建筑物通向其他建筑物的道路按着这条道路的方向以 1 个单位每秒的速度行进。

校长得知这个事情后，决定放弃这个学校逃跑。校长总是位于编号为 n 的行政楼，从零时刻开始需要共 T 秒来逃出行政楼，且逃出行政楼即视为逃出了这个学校。也就是说，如果病毒入侵行政楼的时间不小于 T，则校长能够成功逃离。

有些时候，校长没有足够的时间逃离，因为病毒到达行政楼的时间太快了。

为了让校长能够逃离学校，不得不拆除校园内的一些道路以延缓行政楼的被入侵时间（拆除道路视为在 0 时刻被拆的道路全部消失）。当然，如果使得病毒根本无法到达行政楼，也是可以的。

但是，拆除道路会影响学校的历史气息，且破坏程度定义为拆除的道路中最古老的一条的年龄。请求出保证校长能够安全撤离的情况下，最小的破坏程度。

【输入格式】

从文件 delay.in 中读入数据

第一行包含三个整数：n, m, T。

接下来 m 行，每行描述一条有向道路。每行 4 个整数，si, ti, Li, Yi，分别表示这条道路的起点，终点，长度，这条道路的年龄。

【输出格式】

输出到文件 delay.out 中。

如果不需要拆除任何道路，输出一行两个数：-1 和行政楼的被感染时刻（当然这个时刻大于等于 T），以空格隔开。

否则输出一行包含一个数：最小的破坏程度。

这道题把我们逝去的SPFA CALL 了回来。

60pts

60分思路

对于这部分部分分，我们可以用暴力解决

因为我们要让毁掉的路年龄尽量小，所以我们可以把所有边排序（年龄从大到小），然后一条一条加进去，每加一条就SPFA一次，直到时间不符合要求为止。

60分code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
//#define se second
#define st setpricision
#define Ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N=1e5+5;
vector<pii> a[20005];
pair<pii,pii> edge[100005];
int n,m,T;
bool cmp(pair<pii,pii> x,pair<pii,pii> y){
	return x.second.second>y.second.second;
}
int dis[105];
bool v[105];
int SPFA(){
	memset(dis,0x3f,sizeof(dis));
	queue<int> q;
	q.push(1);
	dis[1]=0;
	v[1]=1;
	while(q.size()){
		int k=q.front();
//		cout<<k<<":";
		q.pop();
		for(int i=0;i<a[k].size();i++){
//			cout<<k<<' '<<a[k][i].first<<' '<<a[k][i].second<<endl;
			if(dis[a[k][i].first]>dis[k]+a[k][i].second){
				dis[a[k][i].first]=dis[k]+a[k][i].second;
				if(!v[a[k][i].first]){
					v[a[k][i].first]=1;
					q.push(a[k][i].first);
				}	
			}
		}
		v[k]=0;
	}
//	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
//	cout<<endl;
	return dis[n];
}
signed main(){
//	freopen("delay.in","r",stdin);
//	freopen("delay.out","w",stdout);
	Ios;
	cin>>n>>m>>T;
	for(int i=1;i<=m;i++){ 
		cin>>edge[i].first.first>>edge[i].first.second>>edge[i].second.first>>edge[i].second.second;
	}
	sort(edge+1,edge+m+1,cmp);
	int k;
	for(int i=1;i<=m;i++){
//		cout<<edge[i].first.first<<' '<<edge[i].first.second<<endl;
		a[edge[i].first.first].push_back({edge[i].first.second,edge[i].second.first});
		k=SPFA();
//		cout<<k<<endl;
		if(k<T){
			cout<<edge[i].second.second;
			exit(0);
		}
	}
	cout<<-1<<' '<<k;
	return 0;
}
/*

*/

100pts

思路

我们可以用二分优化枚举边的部分。

二分mid为：在mid>=这条边的古老程度时这条边就被banned了。

如果不删边都可以逃离，那么输出-1，SPFA(0) (纯粹的最短路)。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
//#define se second
#define st setpricision
#define Ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N=1e5+5;
vector<pair<pii,int> > a[100005];
// pair<pii,pii> edge[100005];
int n,m,T;
// bool cmp(pair<pii,pii> x,pair<pii,pii> y){
	// return x.second.second>y.second.second;
// }
int dis[100005];
bool v[100005];
queue<int> q;
int SPFA(int x){
	memset(dis,0x3f,sizeof(dis));
	q.push(1);
	dis[1]=0;
	v[1]=1;
	while(q.size()){
		int k=q.front();
//		cout<<k<<":";
		q.pop();
		for(int i=0;i<a[k].size();i++){
//			cout<<k<<' '<<a[k][i].first<<' '<<a[k][i].second<<endl;
			if(dis[a[k][i].first.first]>dis[k]+a[k][i].first.second){
				if(x>=a[k][i].second) continue;
				dis[a[k][i].first.first]=dis[k]+a[k][i].first.second;
				if(!v[a[k][i].first.first]){
					v[a[k][i].first.first]=1;
					q.push(a[k][i].first.first);
				}	
			}
		}
		v[k]=0;
	}
//	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
//	cout<<endl;
	return dis[n];
}
signed main(){
//	freopen("delay.in","r",stdin);
//	freopen("delay.out","w",stdout);
	Ios;
	cin>>n>>m>>T; 
	for(int i=1;i<=m;i++){ 
		int x,y,li,yi;
		cin>>x>>y>>li>>yi;
		a[x].push_back({{y,li},yi});
	}
	int l=0,r=0x3f3f3f3f;
	int ans=0;
	int mid=0;
	while(l<=r){
		mid=(l+r)>>1;
		// cout<<mid<<' '<<l<<' '<<r<<'\n';
		int k=SPFA(mid);
		if(k>T||k==0x3f3f3f3f3f3f3f3f){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	if(l==0){
		cout<<-1<<' '<<SPFA(0);
	}
	else cout<<ans;
	return 0;
}
/*

*/

点个赞啊....