食堂有专业的盒饭生产设备，为了人员每顿饭能吃好吃的饭菜，它们总会将a点生产出的盒饭运往加热处加热后再运往b点装车。这些部门非常的高能，它们有时可以生产盒饭，有时又能变身成装车点（不要问我为什么）。
有些部门之间有专门的传送带连接，店长是个非常珍惜时间的人，他希望盒饭从生产出来到运走所花费的时间尽可能的短，但是店长又是一个超级懒人，所以他把计算的工作交给了你
【输入格式】
第一行两个整数n、m，n表示部门数量，m表示传送带数量。出于方便，1号部门是加热处。
接下来m行，每行三个整数u、v、w，表示有一条从u部门到v部门的传送带，传送过去需要w个单位时间。注意传送带是单向的。
接下来一个整数q，表示有q次运送。
接下来q行，每行两个数a、b，表示这一次要将产品从a部门运送到b部门。
【输出格式】
输出q行，每行一个整数，表示这次运送最少需要的时间。若没有传送方案，输出-1。
【样例输入】
5 5
1 2 3
1 3 5
4 1 7
5 4 1
5 3 1
3
4 2
5 3
2 3
【样例输出】
10
13
-1
【数据规模与约定】
30%的数据，n≤100，m≤500，w=1
60%的数据，n≤100，m≤5000
另20%的数据，q=1
100%的数据，2≤n≤3000，m≤100000，2≤a,b≤n，
q≤100000，1≤u,v≤n，1≤w≤10000
有些部门之间可能有多条传送带。
#include<cstdio> #include<cstring> int head[2][6000],next[2][3000],xx[2][6000],to[2][6000],dist[2][3000];/* head[][i]与第i条边具有相同开始节点的上一条边； next[][i]第i个点最后读入的边； xx[][i]第i条边的权值（可以用一个数组）； to[][i]第i条边的终点； dist[][i]第1个点到第i个点的距离*/ int x,y,z,bh=0,q,n,m; bool f[6001]; void dj(int x) { for(int i=2;i<=n;i++){ int min=2100000000,minn; for(int j=next[x][1];j!=0;j=head[x][j]){ if(!f[to[x][j]]&&dist[x][to[x][j]]&&dist[x][to[x][j]]<min){//找从第一个点出发的最短边； min=dist[x][to[x][j]]; minn=j; } } f[to[x][minn]]=true; for(int j=next[x][to[x][minn]];j!=0;j=head[x][j]){ //从第minn个点开始更新； if(!f[to[x][j]]&&((dist[x][to[x][minn]]+xx[x][j]<dist[x][to[x][j]])||(dist[x][to[x][j]]==0))){ dist[x][to[x][j]]=dist[x][to[x][minn]]+xx[x][j]; } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); head[0][i]=next[0][x]; //边表 next[0][x]=i; xx[0][i]=z; to[0][i]=y; head[1][i]=next[1][y]; //边反向建立边表 next[1][y]=i; xx[1][i]=z; to[1][i]=x; } x=next[0][1];f[1]=1; for(;x;){ if(!dist[0][to[0][x]]||dist[0][to[0][x]]>xx[0][x]) dist[0][to[0][x]]=xx[0][x];//将与1相连的边的权值存入dist[1]中; x=head[0][x]; } dj(0); //dijkstra； memset(f,0,3001*sizeof(bool)); f[1]=1; for(x=next[1][1];x;x=head[1][x]){ if(!dist[1][to[1][x]]||dist[1][to[1][x]]>xx[1][x])dist[1][to[1][x]]=xx[1][x];//将与1相连的边的权值存入dist[2]中; } dj(1); //dijkstra； scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d%d",&x,&y); if(dist[1][x]&&dist[0][y]) printf("%d ",dist[0][y]+dist[1][x]);//若x能到1,1能到y，输出最短路； else printf("-1 "); } return 0; }