邮递员送信
题目描述
有一个邮递员要送东西,邮局在节点 1 1 1。他总共要送 n − 1 n-1 n−1 样东西,其目的地分别是节点 2 2 2 到节点 n n n。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 m m m 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 n − 1 n-1 n−1 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数, n n n 和 m m m,表示城市的节点数量和道路数量。
第二行到第 ( m + 1 ) (m+1) (m+1) 行,每行三个整数, u , v , w u,v,w u,v,w,表示从 u u u 到 v v v 有一条通过时间为 w w w 的道路。
输出格式
输出仅一行,包含一个整数,为最少需要的时间。
样例 #1
样例输入 #1
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2
样例输出 #1
83
提示
对于 30 % 30\% 30% 的数据, 1 ≤ n ≤ 200 1 \leq n \leq 200 1≤n≤200。
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 3 1 \leq n \leq 10^3 1≤n≤103, 1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1≤m≤105, 1 ≤ u , v ≤ n 1\leq u,v \leq n 1≤u,v≤n, 1 ≤ w ≤ 1 0 4 1 \leq w \leq 10^4 1≤w≤104,输入保证任意两点都能互相到达。
F l o y d Floyd Floyd 逃课做法(要开O2)
直接套 F l o y d Floyd Floyd
最后的结果是每个点到 1 节点的距离与 1 到每个点的距离之和,注意存储初始距离时保留最短的一条,否则会WA
F l o y d Floyd Floyd做法代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+111;
int n,m,ans=0;
int dis[N][N];
int main(){cin>>n>>m;memset(dis,0x3f,sizeof(dis));for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dis[u][v]=min(dis[u][v],w);//dis[u][v]=w;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}}}for(int i=2;i<=n;i++){ans+=dis[i][1]+dis[1][i];}cout<<ans<<endl;return 0;
}
d i j k s t r a dijkstra dijkstra堆优化
从 1 1 1 跑到其他 2 n 2~n 2 n 节点需要跑一遍 d i j k s t r a dijkstra dijkstra
返回 1 1 1节点也需要跑一遍 d i j k s t r a dijkstra dijkstra
因此我们在 u + n u+n u+n 与 v + n v+n v+n 建一个反图,方便反跑
需要堆优化
答案累加 2 2 2累加到 n n n,反跑后从 2 + n 2+n 2+n 累加到 n ∗ 2 n*2 n∗2即可
AC CODE
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+49999;
int n,m,ans=0;
int dis[N];
vector<pair<int,int> > a[N];
bool vis[N];
void dijkstra(int s){priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;q.push({0,s});while(!q.empty()){pair<int,int> tmp=q.top();q.pop();int x=tmp.second;int y=tmp.first;if(dis[x]<tmp.first)continue;if(vis[x]==1)continue;vis[x]=1;for(int i=0;i<a[x].size();i++){if(dis[a[x][i].first]>y+a[x][i].second){dis[a[x][i].first]=y+a[x][i].second;q.push({dis[a[x][i].first],a[x][i].first});}}}
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;a[u].emplace_back(make_pair(v,w));a[v+n].emplace_back(make_pair(u+n,w));}dijkstra(1);for(int i=2;i<=n;i++){ans+=dis[i];}dijkstra(1+n);for(int i=2+n;i<=n*2;i++){ans+=dis[i];}cout<<ans<<endl;return 0;
}