逃离遗迹
Problem: escape.pas/c/cpp
Input: escape.in
Output: escape.out
Memory Limit: 128 MB
Time Limit: 1 sec
【题目描述】
根据外星人的回信，在遗迹分布着三样道具。当三样道具都拿走后，遗迹就很快自动毁灭，所以必须要在最短时间内离开。遗迹可以看作是由N个房间(编号1..N)和N-l条长度不等通道所组成，并且任意两个房间之间有且只有一条路可以相互到达。现在我们的队员已经在编号为A，B，C的房间内拿到道具，并且准备撤退。由于只有一架直升机，所以只能在一个房间上停留。现在请你决定将直升机停在哪一个房间之上，能够使三人到达该房间的距离之和最短。
【输入格式】
第1行：四个整数N、A、B、C。
第2..N行：每行三个整数u，v，w，表示存在连接房间u，v的通道，长度w。
【输出格式】
第1行：一个整数，表示汇合房间的编号。若存在多个解，输出序号最小的。
第2行：一个整数，表示三人到该房间距离之和。
【输入样例】
5 3 1 4
3 5 5
4 3 9
4 1 7
1 2 1
【输出样例】
4
16
【数据范围】
对于50%的数据：1≤N≤1,000。 对于l00%的数据：1≤N≤20,000。
1≤A,B,C,u,v<=N且A,B,C不相等；u,v不相等。 1≤w≤1,000。
这一题很容易想到用三次spfa，求出所有点分别到a,b,c的最短距离，最后枚举找最优即可（上午想错了，以为只能是ABC三点任意一点，结果任何点都可以。。。）
当然利用数据的特殊性，是一棵树，每两点只有一条路，那么就可以宽搜，第一次找到目标点就肯定是最短的，最后枚举找最优
C++ Code
/*
C++ Code
http://blog.csdn.net/jiangzh7
By jiangzh
*/
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define MAXN 20010
int n,A,B,C;
struct link{int y,z;link *next;};
link *head[MAXN];
int dist[5][MAXN];//dist[x][]表示 x 到任意点的最短距离（或者说任意点到 x 的最短距离）
queue<int> q;
void insert(int x,int y,int z)
{
link *node = new link;
node->y=y;node->z=z;
node->next=head[x];
head[x]=node;
}
void init()
{
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
scanf("%d%d%d%d",&n,&A,&B,&C);
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
insert(y,x,z);
}
}
void spfa(int xxx,int std)
{
dist[xxx][std]=0;q.push(std);
while(!q.empty())
{
int x=q.front();q.pop();
link *node=head[x];
while(node)
{
int y=node->y,z=node->z;
if(dist[xxx][y]>dist[xxx][x]+z)
{
dist[xxx][y]=dist[xxx][x]+z;
q.push(y);
}
node=node->next;
}
}
}
void work()
{
memset(dist,0x07,sizeof(dist));
spfa(1,A);
spfa(2,B);
spfa(3,C);
int ans=0x07070707,k=0;
for(int i=1;i<=n;i++)
if(ans>dist[1][i]+dist[2][i]+dist[3][i])
{
ans=dist[1][i]+dist[2][i]+dist[3][i];
k=i;
}
if(ans==0x07070707) printf("-1");
else printf("%d\n%d",k,ans);
}
int main()
{
init();
work();
return 0;
}
