题目描述
题目描述
有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。
输入输出格式
输入格式：
第一行包括两个整数N和M。
第2到第M+1行，每行三个数字U、V、W，表示从A到B有一条需要W时间的道路。 满足1<=U,V<=N,1<=W<=10000,输入保证任意两点都能互相到达。
【数据规模】
对于30%的数据，有1≤N≤200;
对于100%的数据，有1≤N≤1000,1≤M≤100000。
输出格式：
输出仅一行，包含一个整数，为最少需要的时间。
分析
这题还是一道裸单源最短路呀，dijkstra或spfa跑一边（本人偏好dijkstra），只是要注意把单终点的最短路的每条边倒着存一遍，不就是单源最短路了吗QAQ？
还有就是一定变量不要开错哦。
代码
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m;
struct edge
{
int to,val;
};
int dis[1005],his[1005],vis[1005],visit[1005];
priority_queue<pair<int,int>,vector<pair<int,int > >,greater<pair<int,int> > >q,w;
vector<edge>e[1005],f[1005];
void dijkstra_zheng()
{
for(int i=1;i<=n;i++)
{
dis[i]=2147483647;
}
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(vis[x]==1)
continue;
vis[x]=1;
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i].to;
if(dis[x]+e[x][i].val<dis[y])
{
dis[y]=dis[x]+e[x][i].val;
q.push(make_pair(dis[y],y));
}
}
}
}
void dijkstra_dao()
{
for(int i=1;i<=n;i++)
{
his[i]=2147483647;
}
his[1]=0;
w.push(make_pair(0,1));
while(!w.empty())
{
int x=w.top().second;
w.pop();
if(visit[x]==1)
continue;
visit[x]=1;
for(int i=0;i<f[x].size();i++)
{
int y=f[x][i].to;
if(his[x]+f[x][i].val<his[y])
{
his[y]=his[x]+f[x][i].val;
w.push(make_pair(his[y],y));
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
edge tmp;
tmp.to=y;
tmp.val=z;
e[x].push_back(tmp);
tmp.to=x;
tmp.val=z;
f[y].push_back(tmp);
}
dijkstra_zheng();
dijkstra_dao();
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=dis[i]+his[i];
}
printf("%d",ans);
return 0;
}
转载于:https://www.cnblogs.com/vercont/p/10210084.html
相关资源：JAVA上百实例源码以及开源项目
