HDU 2066 一个人的旅行(Dijkstra)
http://acm.hdu.edu.cn/showproblem.php?pid=2066
题意:给你一个无向图,有s个起点和d个终点,现在要你求s个点中任意一点到d个终点中任意一点的最短距离.
分析:
我们把题目给的原始点,编号1到N,然后我们添加0号点和N+1号点.其中0号点到s个起点的距离为0,d个终点与N+1号点的距离为0.等于是添加了一个超级源点和超级汇点.然后用Dijkstra算法求从0到N+1号点的最短路径即可.
不过原题给的端点可能不连续(即只有3 7 8 9 等数,而不是从1到9),我们需要用map把序号映射到连续的n个数上.
其实本题最简单的方法是假设每个图都有1000个点,我们添加0号点和1001号点即可.然后直接建立具有超级源点和汇点的图,求最短路径值即可.过程中那些原本不存在的点都是孤立的,不用管.(不过应该不会超时)
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
const int maxn = 1000+10;
#define INF 1e9
struct Edge
{
int from,to,dist;
Edge(int f,int t,int d):from(f),to(t),dist(d){}
};
struct HeapNode
{
int d,u;
HeapNode(int d,int u):d(d),u(u){}
bool operator<(const HeapNode &rhs)const
{
return d>rhs.d;
}
};
struct Dijkstra
{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
int d[maxn];
void init(int n)
{
this->n=n;
for(int i=0;i<n;i++) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int dist)
{
edges.push_back(Edge(from,to,dist));
m = edges.size();
G[from].push_back(m-1);
}
void dijkstra()
{
priority_queue<HeapNode> Q;
for(int i=0;i<n;i++) d[i]=INF;
d[0]=0;
Q.push(HeapNode(d[0],0));
memset(done,0,sizeof(done));
while(!Q.empty())
{
HeapNode x=Q.top(); Q.pop();
int u=x.u;
if(done[u]) continue;
done[u]=true;
for(int i=0;i<G[u].size();i++)
{
Edge &e=edges[G[u][i]];
if(d[e.to]>d[u]+e.dist)
{
d[e.to]=d[u]+e.dist;
Q.push(HeapNode(d[e.to],e.to));
}
}
}
}
}DJ;
map<int,int> mp;//将原始城市编号映射到1-n中
int n;
int ID(int x) //新出现的编号 映射成 1-n的序号
{
if(mp[x]==0) mp[x]=++n;
return mp[x];
}
int u[maxn],v[maxn],d[maxn];
vector<int> start;//保存起始点编号
vector<int> end;//保存结束点编号
int main()
{
int T,S,D;
while(scanf("%d%d%d",&T,&S,&D)==3)
{
n=0;
mp.clear();
start.clear();
end.clear();
for(int i=0;i<T;i++)
{
scanf("%d%d%d",&u[i],&v[i],&d[i]);
u[i]=ID(u[i]); //原始编号映射成新的1-n之间的编号
v[i]=ID(v[i]);
}
for(int i=0;i<S;i++)
{
int x; scanf("%d",&x);
start.push_back(ID(x)); //保存映射后的起点编号
}
for(int i=0;i<D;i++)
{
int x; scanf("%d",&x);
end.push_back(ID(x)); //保存映射后的终点编号
}
DJ.init(n+2);
for(int i=0;i<T;i++)
{
DJ.AddEdge(u[i],v[i],d[i]);
DJ.AddEdge(v[i],u[i],d[i]);
}
for(int i=0;i<start.size();i++)
{
DJ.AddEdge(0,start[i],0); //超级源点到所有起点都有一条边
}
for(int i=0;i<end.size();i++)
{
DJ.AddEdge(end[i],n+1,0); //所有终点到超级汇点都有一条边
}
DJ.dijkstra();
printf("%d\n",DJ.d[n+1]); //输出0号点到n+1号点的最短距离
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1716470
HDU的一题........HDU DP动态规
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
这个是杭电hdu的一个分类,新手们可以按照这个来刷题!
hdu1001解题报告
hdu 1574 passed sorce
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了