因为是双向边,所以相当于两条到1的最短路和,先跑spfa然后直接处理询问即可
#include#include #include using namespace std;const int N=50005,inf=1e9;int n,m,b,h[N],cnt,dis[N];bool v[N];struct qwe{ int ne,to,va;}e[N<<2];int read(){ int r=0,f=1; char p=getchar(); while(p>'9'||p<'0') { if(p=='-') f=-1; p=getchar(); } while(p>='0'&&p<='9') { r=r*10+p-48; p=getchar(); } return r*f;}void add(int u,int v,int w){ cnt++; e[cnt].ne=h[u]; e[cnt].to=v; e[cnt].va=w; h[u]=cnt;}int main(){ n=read(),m=read(),b=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); add(x,y,z),add(y,x,z); } queue q; for(int i=1;i<=n;i++) dis[i]=inf; dis[1]=0,v[1]=1,q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); v[u]=0; for(int i=h[u];i;i=e[i].ne) if(dis[e[i].to]>dis[u]+e[i].va) { dis[e[i].to]=dis[u]+e[i].va; if(!v[e[i].to]) { v[e[i].to]=1; q.push(e[i].to); } } } while(b--) { int x=read(),y=read(); printf("%d\n",dis[x]+dis[y]); } return 0;}