【c++】洛谷p1342 请柬题目详解

P1342 请柬

题目背景

在电视时代,没有多少人观看戏剧表演。 Malidinesia 古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。

题目描述

他们已经打印了请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。

这里的公交系统是非常特殊的：共有 n 个站点和 m 个线路，所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。

学生每天早上从总部所在的 1 号站点出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

输入格式

输入的第一行是两个整数，代表站点个数 n 和线路条数 m。

第 2 到第 (m+1) 行，每行三个整数 u, v, w代表存在一条从 u 出发到达v 的线路，费用为 w。

输出格式

输出一行一个整数，表示最小费用。

输入输出样例

输入 #1复制

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

输出 #1复制

210 

说明/提示

数据规模与约定

对于 100\%100% 的数据，保证：

• 1≤n,m≤10^6。
• 1≤u,v≤n,1≤w≤10^9。
• 从 1 出发可以到达所有的站点。

这道题的只需要将数据正着跑一遍再反着跑一边即可 

题解如下

#include
#include
#include
#include
#include
#include
using namespace std;
struct node{
	long long int u,v,w,next;
}e[2010102];
struct wc{
	long long int zhi,bh;
	bool operator  a.zhi;
	}
};
int ecnt=0;
int head[2000005];
void add(int u,int v,int w){
	e[++ecnt].u=u;
	e[ecnt].w=w;
	e[ecnt].v=v;
	e[ecnt].next=head[u];
	head[u]=ecnt;
}
long long int m,n;
long long int tmd[2000050];
long long int dis[2000005],vis[1000005];
void dij(){
	priority_queueq;
	for(int i=1;idis[x]+e[i].w){
				dis[e[i].v]=dis[x]+e[i].w;
				if(!vis[e[i].v]){
					q.push((wc){dis[e[i].v],e[i].v});
				}
			}
		}
	}
}
void dij1(){
	priority_queueq;
	for(int i=n+1;itmd[x]+e[i].w){
				tmd[e[i].v]=tmd[x]+e[i].w;
				if(!vis[e[i].v]){
					q.push((wc){tmd[e[i].v],e[i].v});
				}
			}
		}
	}
}

int ans=0;
int main(){
	cin>>n>>m;
	for(int i=1;i>a12>>b1>>c1;
		add(a12,b1,c1);
		add(b1+n,a12+n,c1);//这道题考虑到去和回两个过程，需要记录两个表，避免重复所以第二个表每一个坐标都加n
	}
	dij();
	dij1();
	long long int w=0;
	for(int i=1;i