hihocoderプログラミング練習試合78-Dぬかるみの道(最短)

https://hihocoder.com/contest/offers78/problem/4
 
POINT:
起点からある点までには必ず複数の道があり、これらの道は(a,b)と抽象化することができ、aは通過する経路の本数を表し、bは通過する経路の全長を表す.
では、答えは=a*日数+bです.
では、各点の多対(a,b)を見つけなければなりません.日数が多い場合、明らかにaが小さい方が有利ですが、日数が少ない場合、aが大きい方が有利かもしれません. 
もちろん、これらの比較は、aが決定した場合、bが最小である.これは最短で処理できます.
それから1つの点を尋ねるたびに、私たちはこの点の(a,b)対数を遍歴して、最小の答えを取ります.
 
dis[x][y]を開くと、y辺からxまでの最短距離を表します.
構想は,各y(各a)に対して,最小のdis[x][y](最小のb)を探し出すことである.
y>=nに気づいたときは、検索しないで、必ずまた繰り返しの道を歩きます.
そして私たちはすべてのdis[x][y]を探して、私たちはすべてのxに対して、y=1からy=nまで、すべてを走ることはできません.これはtleに違いない.
接頭辞の最小値を維持し、現在のdis[x][y]がこの最小値より大きい場合、このペアには価値がありません.前の最小値で対応したaはきっとこのAより小さいからです.bもこのB=dis[x][y]より小さい.Ax+B>ax+bは必ず成立するので価値がありません.(このmain関数におけるQ回クエリに対応する前の前処理操作は,主にqqというvectorに現れる)
ヒープ最適化リロード演算子
 

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
const int N = 1111+55;
const int inf = 0x3f3f3f3f;
vectorG[N];
vectorW[N];
struct node
{
	int a,b,c;
	node(int aa,int bb,int cc)
	{
		a=aa;b=bb;c=cc;
	}
	bool friend operator < (node a,node b)
	{
		return a.a>b.a;
	}
};
int n,m,Q;

int dis[N][N],vis[N][N];
void dij()
{
	memset(dis,inf,sizeof dis);memset(vis,0,sizeof vis);
	dis[1][0]=0;
	priority_queueq;
	q.push(node(0,1,0));
	while(!q.empty()){
		node x = q.top();
		q.pop();
		int u=x.b,p=x.c;
		if(vis[u][p]||p>n) continue;
		vis[u][p]=1;
		for(int i=0;i=dis[u][p]+w){
				dis[v][p+1]=dis[u][p]+w;
				q.push(node(dis[v][p+1],v,p+1));
			}
		}
	}

}

vector qq[N];

int main()
{
	scanf("%d%d%d",&n,&m,&Q);
	for(int i=1;i<=m;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		G[x].push_back(y);G[y].push_back(x);
		W[x].push_back(w);W[y].push_back(w);
	}
	dij();
	for(int i=2;i<=n;i++){
		int Min=inf;
		for(int j=1;j<=n;j++){
			if(dis[i][j]>=Min) ;
			else{
				Min=dis[i][j];
				qq[i].push_back(node(j,dis[i][j],0));
			}
		}
	}
	while(Q--){
		int i,j;scanf("%d%d",&j,&i);
		if(j==1) printf("0
");
		else{
			LL ans=0x3f3f3f3f3f3f3f3f;
			for(int k=0;k