欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最短路(SPFA - 反向建边)

程序员文章站 2022-06-20 09:03:08
...

题目描述
  给定一个 nnn 点 mmm 边的有向带权图表示一座城市,起点为 111 。送餐小哥需要给 nnn 个客户送外卖,第 iii 个客户的家在第 iii 号点。由于他的车子容量很小,所以一次只能容纳一份外卖,所以送达外卖之后就要回到起点取新的外卖送下一单,直到全部送到位置。
  有向图保证联通。外卖小哥一定走的最短路。
  求送餐小哥走的总路程。
输入格式
  第一行一个整数 T,表示数据组数。
  对于每组数据,第一行两个整数 n 和 m 。
  接下来 m 行,每行三个整数 ui,vi,ci​ 表示每条有向边。
输出格式
  对于每组数据,输出一行一个整数表示答案。
数据范围
  对于 20%20%20% 的数据: 0<n≤1000 ,
  对于 40%40%40% 的数据: 0<n≤3000,
  对于 60%60%60% 的数据: 0<n≤10000,
  对于 100%100%100% 的数据: 0<n≤20000,m≤60000,1≤T≤10,0≤ci≤109,1≤ui,vi≤n
  保证答案在 long long 范围内。
样例输入
  2
  2 2
  1 2 13
  2 1 33
  4 6
  1 2 10
  2 1 60
  1 3 20
  3 4 10
  2 4 5
  4 1 50
样例输出
  46
  210

  哭了, infinf 写成 intint 型,DijkDijk 超时只过了 88 组,spfaspfa稳过,刚开始跑一遍 spfaspfa 可以得到 11 到任意点的最短距离,如果想到得到任意点到 11 的最短距离,反向建图再跑一遍 spfaspfa 即可。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int maxn=2e4+10;
const int maxm=6e4+10;
int head[maxn],cnt,from[maxm],to[maxm];
int n,m;

bool vis[maxn];
ll dis[maxn],cost[maxm];

struct Edge{
	int u,v,next;
	ll w;
}edge[maxm];

void addedge(int u,int v,ll w){
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}

void spfa(int s){
	for(int i=1;i<=n;i++){
		vis[i]=false; dis[i]=inf;
	}	
	queue<int>q; q.push(s); dis[s]=0; vis[s]=true;
	while(!q.empty()){
		int u=q.front(); q.pop(); vis[u]=false;
		for(int i=head[u];i!=-1;i=edge[i].next){
			if(dis[edge[i].v]>dis[u]+edge[i].w){
				dis[edge[i].v]=dis[u]+edge[i].w;
				if(!vis[edge[i].v]){
					vis[edge[i].v]=true;
					q.push(edge[i].v);
				}
			}
		}
	}
}

int main(){
	int T; scanf("%d",&T);
	while(T--){ cnt=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) head[i]=-1;
		for(int i=1;i<=m;i++){
			scanf("%d%d%lld\n",&from[i],&to[i],&cost[i]);
			addedge(from[i],to[i],cost[i]);
		}
		spfa(1); ll ans=0;
		for(int i=1;i<=n;i++) ans+=dis[i];
		cnt=0;
		for(int i=1;i<=n;i++) head[i]=-1;
		for(int i=1;i<=m;i++) addedge(to[i],from[i],cost[i]);
		spfa(1);
		for(int i=1;i<=n;i++) ans+=dis[i];
		printf("%lld\n",ans);
	}
	return 0;
}

DijkDijk 链式前向星建图,过 88 组。

//TLE
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,int>P;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int maxn=2e4+10;
const int maxm=6e4+10;
ll dis[maxn];
int n,m;
int u[maxm],v[maxm]; ll w[maxm];

struct Edge{
	int to; ll cost;	
	Edge(){}
	Edge(int to,ll cost):to(to),cost(cost){};
}edge[maxm]; 

vector<Edge>G[maxn];

void Dijk(){
	for(int i=1;i<=n;i++) dis[i]=inf;
	priority_queue<P>pq; pq.push(P(0,1)); dis[1]=0;
	while(!pq.empty()){
		P p=pq.top(); pq.pop();
		int v=p.second;
		if(dis[v]<p.first) continue;
		for(int i=0;i<G[v].size();i++){
			Edge edge=G[v][i];
			if(dis[edge.to]>dis[v]+edge.cost){
				dis[edge.to]=dis[v]+edge.cost;
				pq.push(P(edge.cost,edge.to));
			}
		}
	}	
}

int main(){
	int T; scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) G[i].clear();
		for(int i=1;i<=m;i++){
			scanf("%d%d%lld",&u[i],&v[i],&w[i]);
			G[u[i]].push_back(Edge(v[i],w[i])); 
		}
		Dijk(); ll ans=0;
		for(int i=1;i<=n;i++){
			ans+=dis[i]; G[i].clear();
		}
		for(int i=1;i<=m;i++) G[v[i]].push_back(Edge(u[i],w[i]));
		Dijk(); 
		for(int i=1;i<=n;i++){
			ans+=dis[i];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

DijkDijk vectorvector 建图,过 66 组。

//TLE
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,int>P;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int maxn=2e4+10;
const int maxm=6e4+10;
int head[maxn],cnt,from[maxm],to[maxm];
int n,m;
ll dis[maxn],cost[maxm];

struct Edge{
	int u,v,next;
	ll w;
}edge[maxm];

void addedge(int u,int v,ll w){
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}

void Dijk(int s){
	for(int i=1;i<=n;i++) dis[i]=inf;
	priority_queue<P>pq; pq.push(P(0,s)); dis[s]=0;
	while(!pq.empty()){
		P p=pq.top(); pq.pop();
		int v=p.second;
		if(dis[v]<p.first) continue;
		for(int i=head[v];i!=-1;i=edge[i].next){
			if(dis[edge[i].v]>dis[v]+edge[i].w){
				dis[edge[i].v]=dis[v]+edge[i].w;
				pq.push(P(dis[edge[i].v],edge[i].v));
			}
		}
	}
}

int main(){
	int T; scanf("%d",&T);
	while(T--){ cnt=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) head[i]=-1;
		for(int i=1;i<=m;i++){
			scanf("%d%d%lld",&from[i],&to[i],&cost[i]);
			addedge(from[i],to[i],cost[i]);
		}
		Dijk(1); ll ans=0;
		for(int i=1;i<=n;i++) ans+=dis[i];
		cnt=0;
		for(int i=1;i<=n;i++) head[i]=-1;
		for(int i=1;i<=m;i++) addedge(to[i],from[i],cost[i]);
		Dijk(1);
		for(int i=1;i<=n;i++) ans+=dis[i];
		printf("%lld\n",ans);
	}
	return 0;
}
相关标签: Graph