https://www.luogu.org/problemnew/show/1342
题目描述
在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。
这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。
输入输出格式
输入格式：
第1行有两个整数n、m(1<=n,m<=1000000)，n是站点的个数，m是线路的个数。
然后有m行，每行描述一个线路，包括3个整数，起始点，目的地和价格。
总部在第1个站点，价钱都是整数，且小于1000000000。
输出格式：
输出一行，表示最小费用。
输入输出样例
说明
【注意】
此题数据规模较大，需要使用较为高效的算法，此题不设小规模数据分数。
1 #include <cstdio> 2 #include <queue> 3 4 #define LL long long 5 inline void read(int &x) 6 { 7 x=0; register char ch=getchar(); 8 for(; ch>'9'||ch<'0'; ) ch=getchar(); 9 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 10 } 11 12 const int N(1000005); 13 int sumedge,head[N][2]; 14 int _v[N][2],_nex[N][2],_w[N][2]; 15 16 inline void ins(int u,int v,int w) 17 { 18 _v[++sumedge][0]=v; 19 _nex[sumedge][0]=head[u][0]; 20 _w[sumedge][0]=w; head[u][0]=sumedge; 21 _v[sumedge][1]=u; 22 _nex[sumedge][1]=head[v][1]; 23 _w[sumedge][1]=w; head[v][1]=sumedge; 24 } 25 26 bool vis[N]; 27 LL dis[N],ans; 28 29 struct Node { 30 int pos; LL dis; 31 bool operator < (const Node &x)const 32 { 33 return dis>x.dis; 34 } 35 }u,v; 36 37 inline void Dijkstra(int n,int op) 38 { 39 std::priority_queue<Node>que; 40 for(int i=1; i<=n; ++i) 41 dis[i]=0x3f3f3f3f,vis[i]=0; 42 dis[1]=u.dis=0; u.pos=1; que.push(u); 43 for(; !que.empty(); ) 44 { 45 u=que.top(); que.pop(); 46 if(vis[u.pos]) continue; vis[u.pos]=1; 47 for(int i=head[u.pos][op]; i; i=_nex[i][op]) 48 { 49 v.pos=_v[i][op]; 50 if(dis[v.pos]<=dis[u.pos]+_w[i][op]) continue; 51 v.dis=dis[v.pos]=dis[u.pos]+_w[i][op]; 52 que.push(v); 53 } 54 } 55 for(int i=1; i<=n; ++i) ans+=1ll*dis[i]; 56 } 57 58 int Presist() 59 { 60 int n,m; 61 read(n),read(m); 62 for(int u,v,w,i=1; i<=m; ++i) 63 read(u),read(v),read(w),ins(u,v,w); 64 for(int i=0; i<2; ++i) Dijkstra(n,i); 65 printf("%lld ",ans); 66 return 0; 67 } 68 69 int Aptal=Presist(); 70 int main(int argc,char**argv){;}