Nowcoder Practice 61 D.最短路变短了 (最短路）

题目传送门

题意：给定有向带权图，求将一条边反向是否使最短路变短。

思路：显然修改后若不走这条边最短路不会变短，若走这条路需要比较d[v]+w+d1[u]与d[n]的关系 （d[ i ]表示到1的距离，d1[ i ]表示到n的距离。

SPFA 链式

#include<bits/stdc++.h>
using namespace std;
#define mst(a) memset(a,0,sizeof a) 
typedef long long ll;
const int N=1e5+5,M=2e5+5,inf=0x3f3f3f3f;
ll n,m,d[N],h[N],d1[N],vis[N],q,cnt=1;
struct edge{
	ll to,nt,w;
}e[M];
ll a[M][3];
void add(int u,int v,ll w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nt=h[u];
	h[u]=cnt++;
}
void spfa(ll *dis,ll be){
	 queue<int>q;
	for(int i=1;i<=n;i++) dis[i]=1e14,vis[i]=0;
	 //for(int i=1;i<=n;i++) printf("dis[%d]=%d\n",i,dis[i]);
	 q.push(be);
	 vis[be]=1;
	 dis[be]=0;
	 while(q.size()){
	 	int u=q.front();q.pop();vis[u]=0;
		for(int i=h[u];i;i=e[i].nt){
			ll v=e[i].to,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]) vis[v]=1,q.push(v);
			}
		} 
	 }
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		for(int j=0;j<3;j++)
			cin>>a[i][j];
		add(a[i][0],a[i][1],a[i][2]);
	}
	spfa(d,1);
	mst(h),cnt=1;
	for(int i=1;i<=m;i++)
		e[i].nt=0;
	for(int i=1;i<=m;i++){
		add(a[i][1],a[i][0],a[i][2]);
	}
	spfa(d1,n);
	//for(int i=1;i<=n;i++) printf("d=%d,d1=%d\n",d[i],d1[i]);
	cin>>q;
	while(q--){
		int x;
		cin>>x;
		if(d[a[x][1]]+a[x][2]+d1[a[x][0]]<d[n])
			puts("YES");
		else puts("NO");
	}
	return 0;
}

SPFA 邻接矩阵

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e5+5,M=2e5+5; 
vector<PII >e[N],e1[N];
ll d[N],d1[N],u[M],v[M],c[M],n,m,q;
void spfa(int be,ll d[],vector<PII >e[]){
	for(int i=1;i<=n;i++) d[i]=1e14;
	d[be]=0;
	queue<int>q;
	q.push(be);
	while(q.size()){
		int u=q.front();q.pop();
		for(auto it:e[u]){
			int v=it.first,w=it.second;
			if(d[v]>d[u]+w)
				d[v]=d[u]+w,q.push(v);
		} 
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>c[i];
		e[u[i]].push_back({v[i],c[i]});
		e1[v[i]].push_back({u[i],c[i]});
	}
	spfa(1,d,e),spfa(n,d1,e1);
	//for(int i=1;i<=n;i++) printf("%d,%d\n",d[i],d1[i]);
	cin>>q;
	while(q--){
		int x;
		cin>>x;
		if(d[v[x]]+c[x]+d1[u[x]]<d[n])
			puts("YES");
		else puts("NO");
	}
	return 0;
}