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