测试结果

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50004;
const int maxm = 200005;
int head[maxm],cnt = 1;
int n,m;
int dis[maxn],vis[maxn],tmp[maxn];
priority_queue<pair<int,int> > q;
struct node{
  int to,nxt,w;
}edge[maxm];
void Input(int u,int v,int w){
  edge[cnt] = {v,head[u],w};
  head[u] = cnt++;
}
void Dijkstra(int s){
  dis[s] = 0;
  q.push({0,s});
  while(!q.empty()){
  	int u = q.top().second; q.pop();
  	if(vis[u]) continue; vis[u] = 1;
  	for(int i = head[u];~i;i = edge[i].nxt){
  	  int v = edge[i].to, w = edge[i].w;
	  if(dis[v] > dis[u] + w){
	  	dis[v] = dis[u] + w;
	  	q.push({-dis[v],v});
	  }
	}
  }
}
int main(){
  int s;
  cin >> n >> m >> s;
  for(int i = 1;i <= n;++i) dis[i] = INT_MAX;
  for(int i = 1;i <= m;++i) head[i] = -1;
  for(int i = 1;i <= m;++i){
  	int u,v,w;
  	cin >> u >> v >> w;
  	Input(u,v,w);
  	Input(v,u,w);
  }
  Dijkstra(1);
  for(int i = 1;i <= s;++i){
  	int u,v;
  	cin >> u >> v;
  	cout << dis[u] + dis[v] << endl;
  } 
//  Bellman_Ford(s);
  return 0;
}