描述 Description
Farmer John 有 B 头奶牛 (1<=B<=25000)，有 N(2*B<=N<=50000) 个农场，编号 1-N，有 M(N-1<=M<=100000)条双向边，第 i 条边连接农场 R_i 和 S_i(1<=R_i<=N;1<=S_i<=N)，该边的长度是 L_i(1<=L_i<=2000)。居住在农场 P_i 的奶牛 A(1<=P_i<=N)，它想送一份新年礼物给居住在农场 Q_i(1<=Q_i<=N)的奶牛 B，但是奶牛 A 必须先到 FJ(居住在编号 1 的农场)那里取礼物，然后再送给奶牛 B。你的任务是：奶牛 A 至少需要走多远的路程？
描述一条边的信息。
第 M+2..M+B+1 行：共 B 行，每行两个整数 P_i 和 Q_i，表示住在 P_i 农场的奶牛送礼物给住在 Q_i 农场的奶牛。
输出格式 OutputFormat
共 B 行，每行一个整数，表示住在 P_i 农场的奶牛送礼给住在 Q_i 农场的奶牛至少需要走的路程
样例输入 SampleInput
10 20 5
1 3 9
6 1 9
5 8 6
8 2 10
10 9 8
10 3 4
8 6 3
3 10 6
8 2 1
1 2 4
4 8 3
3 7 7
3 5 4
8 6 8
9 6 1
6 8 5
1 9 5
6 2 7
1 4 10
4 3 6
7 8
9 6
5 2
10 4
1 3
样例输出 SampleOutput
21
11
15
21
9
来源 Source
Silver
代码 Code
SPFA.
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/11.27;
int i,j,t,n,m,l,r,k,z,y,x;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct edge
{
int to,next,val;
}e[200005];
int head[50005],dis[50005];
bool used[50005];
int b,cnt;
deque <int> q;
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
inline void spfa(int s)
{
int i,j,t,u,v,w;
for (i=1;i<=n;i++) dis[i]=inf;
while (!q.empty()) q.pop_front();
memset(used,false,sizeof(used));
q.push_back(s);dis[s]=0;used[s]=true;
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;w=e[i].val;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
if (!q.empty())
{
if (dis[v]>dis[q.front()]) q.push_back(v);
else q.push_front(v);
}
else q.push_back(v);
}
}
}
}
}
int main()
{
read(n);read(m);read(b);
for (i=1,cnt=0;i<=m;i++)
{
read(x);read(y);read(z);
ins(x,y,z);
ins(y,x,z);
}
spfa(1);
for (i=1;i<=b;i++)
{
read(x);read(y);
printf("%d\n",dis[x]+dis[y]);
}
return 0;
}