$Floyd$做法

题意

送快递,每次1个 效率真的不高

送完要往返回到点1

所以就是求

求1到各点之间的最短路 和 各点到1的最短路 之和

思路

我一开始想用 $dijkstra$优化版+链式前向星 写的

但一看数据

$1≤n≤10^3,1≤m≤10^5$

真的不高 爆率真的不高

所以我又改变主意,改用$floyd$

主要写起来简单

废话不多说

$floyd$模板再改一下输出的地方就行了

代码

#include<iostream>
#include<cstring>
#define N 1145
#define M 114514
using namespace std;
int n,m,sum=0;
/*struct ed
{
    int u,v,w;
    int next;
};
ed edge[M];
int h[M],tot;
void push(int u,int v,int w)
{
    edge[++tot]={u,v,w,h[u]};
    h[u]=tot;
}*/
int dis[N][N];
void floyd()
{
    for(int k=1;k<=n;k++)//中介点
        for(int i=1;i<=n;i++)//起点
            for(int j=1;j<=n;j++)//终点
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];//更新最短路
}
int main()
{
    memset(dis,0x3f,sizeof dis);//正无穷
	cin>>n>>m;//输入
    for(int i=1;i<=n;i++)//自环(对角线)初始化
        dis[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;//输入
        //push(u,v,w);
        dis[u][v]=min(dis[u][v],w);//取最短路
    }
    floyd();//floyd
    for(int i=2;i<=n;i++)
    {
        sum+=dis[1][i]+dis[i][1];//求总共跑的路径
    }
    cout<<sum;//输出
    return 0;//完结散花
}

Dijkstra反向存图做法

思路：

去：正常建图

回：反向建图

然后Dijkstra两遍即可

代码：

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> a1[2005],a2[2005];
int f1[2005],f2[2005],n,m;
long long ans;
int main(){
    cin>>n>>m;
    for(int i=0,u,v,w;i<m;i++){
        cin>>u>>v>>w;
        a1[u].push_back({v,w});
        a2[v].push_back({u,w});
    }memset(f1,0x3f,sizeof f1);
    memset(f2,0x3f,sizeof f2);
    f1[1]=0,f2[1]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q1;
    q1.push({0,1});
    while(!q1.empty()){
        int u=q1.top().second,d=q1.top().first;
        q1.pop();
        if(d>f1[u])continue;
        for(int i=0;i<a1[u].size();i++) {
            int v=a1[u][i].first,w=a1[u][i].second;
            if(f1[v]>f1[u]+w){
                f1[v]=f1[u]+w;
                q1.push({f1[v],v});
            }
        }
    }priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q2;
    q2.push({0, 1});
    while(!q2.empty()){
        int u=q2.top().second,d=q2.top().first;
        q2.pop();
        if(d>f2[u])continue;
        for(int i=0;i<a2[u].size();i++){
            int v=a2[u][i].first;
            int w=a2[u][i].second;
            if(f2[v]>f2[u]+w){
                f2[v]=f2[u]+w;
                q2.push({f2[v],v});
            }
        }
    }for(int i=2;i<=n;i++)ans+=f1[i]+f2[i];
    cout<<ans;
    return 0;
}

题意

求从节点1到其他节点的来回最短路。

思路

一看到来回二字，首先就是反向建图dijkstra，两遍过。

题目好水，写一次就A了，甚至没调试。

反向建图就是把图反过来再建一次，然后反图的最短路就是回来的最短路。

代码

废话不多说，上代码！

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N(2e3);
vector<pair<int,int>> a1[N];//图1 
vector<pair<int,int>> a2[N];//图2 
int f1[N];//最短路1 
int f2[N];//最短路2 
int n;
int main(){
	void dijkstra();
	int m(0);
	cin>>n>>m;
	while(m--){//不需要m了 
		int u(0);
		int v(0);
		int w(0);
		cin>>u>>v>>w;
		a1[u].push_back({v,w});//正向建图 
		a2[v].push_back({u,w});//反向建图 
	}
	dijkstra();
	int ans(0);
	for(int i(1);i<=n;i++)
		ans+=f1[i]+f2[i];//加上来去的时间 
	cout<<ans;
	return 0;
}
void dijkstra(){
	void initialize();
	initialize();
	priority_queue<pair<int,int>> q1;//主打一个大头堆优化
	bool vis1[n+1]{};
	q1.push({0,1});
	while(!q1.empty()){//dijkstra，不必多言。 
		int u(q1.top().second);
		q1.pop();
		int len(a1[u].size());
		for(int i(0);i<len;i++){
			int v(a1[u][i].first);
			int w(a1[u][i].second);
			if(f1[v]>f1[u]+w){
				f1[v]=f1[u]+w;
				if(!vis1[v])
					q1.push({-f1[v],v});
			}
		}
	}
	priority_queue<pair<int,int>> q2;//再来一遍
	bool vis2[n+1]{};
	q2.push({0,1});
	while(!q2.empty()){
		int u(q2.top().second);
		q2.pop();
		int len(a2[u].size());
		for(int i(0);i<len;i++){
			int v(a2[u][i].first);
			int w(a2[u][i].second);
			if(f2[v]>f2[u]+w){
				f2[v]=f2[u]+w;
				if(!vis2[v])
					q2.push({-f2[v],v});
			}
		}
	}
}
void initialize(){
	memset(f1,0x3f,sizeof f1);
	memset(f2,0x3f,sizeof f2);
	f1[1]=0;
	f2[1]=0; 
}

提示

这题数据真的不大，所以可以用floyd，但我不想写

想用floyd的看潘伟明的题解。

Dijkstra反向存图做法

#include<iostream>
#include<string> 
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n,m,x,dis[114514];
vector <pair<int,int>> edges[114514];
vector <pair<int,int>> fedges[114514];  //用来存反图 
priority_queue <pair<int,int>> q;
bool vis[114514];
int dist[114514];
int sum=0;

void init(){							//初始化函数 
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[1]=0;
}

int main()
{
	cin >> n >> m ;
	int u,v,w;
	for (int i=1;i<=m;i++)
	{
		cin >> u >> v >> w;
		edges[u].push_back({v,w});
		fedges[v].push_back({u,w}); 
	}
	
	init();								//普通dijkstra流程 
	q.push({0,1});
	while(!q.empty()){
		u=q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u]=1;
		int sz=edges[u].size();
		for (int j=0;j<sz;j++){
			v=edges[u][j].first;
			w=edges[u][j].second;
			if (dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
	for (int i=1;i<=n;i++)				//路径加和 
	{
		sum+=dis[i];
	}
	
	init();
	q.push({0,1});
	while(!q.empty()){
		u=q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u]=1;
		int sz=fedges[u].size();
		for (int j=0;j<sz;j++){
			w=fedges[u][j].second;
			v=fedges[u][j].first;
			if (dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
	
	for (int i=1;i<=n;i++)
	{
		sum+=dis[i];
	}
	
	cout << sum;
	return 0;
 }