```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <deque>
#define ll long long
using namespace std;
int n,m,b,v[100001],w[100001],next[100001],st[100001],fr,to,wi,topt,p;
ll dis[50001];
bool f[50001];
void add (int x,int y,int z)
{
w[++topt]=z;
v[topt]=y;
next[topt]=st[x];
st[x]=topt;
}
int main()
{
deque<int>q; q.clear();
scanf("%d%d%d",&n,&m,&b);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&fr,&to,&wi);
add(fr,to,wi);
add(to,fr,wi);
}
for (int i=1;i<=50000;i++) dis[i]=0x7fffffff;
dis[1]=0; q.push_back(1); f[1]=1;
while (!q.empty())
{
int x=q.front(); q.pop_front(); f[x]=0;
p=st[x];
while (p)
{
if (dis[x]+w[p]<dis[v[p]])
{
dis[v[p]]=dis[x]+w[p];
if (!f[v[p]])
{
if (dis[v[p]]<dis[x]) q.push_front(v[p]);else q.push_back(v[p]);
f[v[p]]=1;
}
}
p=next[p];
}
}
for (int i=1;i<=b;i++)
{
int xx,yy; scanf("%d%d",&xx,&yy);
printf("%d\n",dis[xx]+dis[yy]);
}
return 0;
}
```
by syh0313 @ 2017-08-24 21:24:45
你加个读入优化试试
by moye到碗里来 @ 2017-08-24 21:29:31
@[一晴](/space/show?uid=14865)
by moye到碗里来 @ 2017-08-24 21:30:57
```cpp
int read()
{
int ret=0,ok=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')ok=-1;ch=getchar();}
for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
return ret*ok;
}
```
by Hammer_cwz_77 @ 2017-08-24 21:54:43
stl本来就挺慢的,最好别用吧
by Hammer_cwz_77 @ 2017-08-24 21:55:08
@[moye到碗里来](/space/show?uid=52576) @[神犇(cwz)](/space/show?uid=34939) 试过了,没用
莫不是被卡常?
by syh0313 @ 2017-08-25 20:08:44
@[一晴](/space/show?uid=14865) 那可能就是卡常了
by moye到碗里来 @ 2017-08-25 20:24:13
@[moye到碗里来](/space/show?uid=52576) 恩
by syh0313 @ 2017-08-25 20:32:13
手动开o2又不让.......
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <deque>
#define ll long long
#pragma GCC optimize (2)
#pragma G++ optimize (2)
using namespace std;
int n,m,b,v[100001],w[100001],next[100001],st[100001],fr,to,wi,topt,p;
ll dis[50001];
bool f[50001];
int read()
{
int x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
return x;
}
void write(int x)
{
int num = 0; char c[15];
while(x) c[++num] = (x%10)+48, x /= 10;
while(num) putchar(c[num--]);
putchar('\n');
}
void add (int x,int y,int z)
{
w[++topt]=z;
v[topt]=y;
next[topt]=st[x];
st[x]=topt;
}
int main()
{
deque<int>q; q.clear();
n=read(); m=read(); b=read();
for (int i=1;i<=m;i++)
{
fr=read(); to=read(); wi=read();
add(fr,to,wi);
add(to,fr,wi);
}
for (int i=1;i<=50000;i++) dis[i]=0x7fffffff;
dis[1]=0; q.push_back(1); f[1]=1;
while (!q.empty())
{
int x=q.front(); q.pop_front(); f[x]=0;
p=st[x];
while (p)
{
if (dis[x]+w[p]<dis[v[p]])
{
dis[v[p]]=dis[x]+w[p];
if (!f[v[p]])
{
if (dis[v[p]]<dis[x]) q.push_front(v[p]);else q.push_back(v[p]);
f[v[p]]=1;
}
}
p=next[p];
}
}
for (int i=1;i<=b;i++)
{
int xx,yy; xx=read(); yy=read();
write(dis[xx]+dis[yy]);
}
return 0;
}
```
by syh0313 @ 2017-08-25 20:43:01
那就尴尬了
by Hammer_cwz_77 @ 2017-08-25 21:50:46