抄代码的人RE！
(第一次写题解，有点小激动)
其实这一题也是卡了我好久的，就因为题目意思理解错了（虽然是一遍过）
先讲一下思路
邮递员要送N-1样东西&&这个邮递员每次只能带一样东西，也就是求从1点出发，到其他每一个点走一个来回的最短距离和；
思路就来了：
思路一：跑n遍Dijkstra，依次求出从1点出发，到其他每一个点走一个来回的最短距离。
结果------原地爆炸------3个TLE；
思路二：跑两遍Dijkstra
跑两遍怎么就能求的出来呢？
第一遍：毫无疑问求出1到其他每一个点走一遍的最短距离；
第二遍：反向存图，从每个点到1的最短距离；
然后相加就好啦
结果--------
恭喜你通过了此题！！！
~代码来也~~~
#include<bits/stdc++.h>//万能头文件
#define MAXN 1001//定义常量
#define MAXM 100001//同上
#define lots_of_money namespace std
using lots_of_money//路费
struct edge//数组模拟临接表储存
{
int to;
int next;
int val;
}edg1[MAXM],edg2[MAXM];
int dis1[MAXN],dis2[MAXN];
int head1[MAXN],head2[MAXN];
bool vis[MAXN];
int dis[MAXN];
int top=0;//边的个数
int total;//最终答案
int n,m;
void join(int u,int v,int val)//存储一条边
{
top++;
edg1[top].next=head1[u];//正向存储
edg1[top].to=v;
edg1[top].val=val;
head1[u]=top;
edg2[top].next=head2[v];//反向存储
edg2[top].to=u;
edg2[top].val=val;
head2[v]=top;
}
void into()//输入
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,val;
cin>>u>>v>>val;
join(u,v,val);
}
}
void csh()//初始化
{
memset(vis,0,sizeof(vis));
for(int i=2;i<=n;i++)
dis[i]=INT_MAX;
dis[1]=0;
}
void djstl(edge *edge,int *head)//传数组用指针
{
for(int l=1;l<n;l++)//Dijkstra
{
int k=0,minn=INT_MAX;
for(int i=1;i<=n;i++)
if(!vis[i]&&dis[i]<minn)
minn=dis[k=i];
if(k==0) break;
vis[k]=1;
for(int i=head[k];i;i=edge[i].next)
if(dis[k]+edge[i].val<dis[edge[i].to])
dis[edge[i].to]=dis[k]+edge[i].val;
}
}
int main()
{
into();
csh();
djstl(edg1,head1);
for(int i=2;i<=n;i++)//加上去的时间
total+=dis[i];
csh();
djstl(edg2,head2);
for(int i=2;i<=n;i++)//加上回来的时间
total+=dis[i];
cout<<total<<endl;
return true;
}
