#include<iostream>
#include<string>
#include<string.h>
#include<vector>
#include<stdio.h>
#include <queue>
#include<algorithm>
using namespace std;
const int maxn=1005;

struct Edge
{
	int u;
	int v;
	int dis;
	int cos;
	Edge(int a,int b,int c,int d):u(a),v(b),dis(c),cos(d){}
};

vector<Edge>G[maxn];
int inq[maxn],d[maxn],c[maxn];
void init()
{
	for(int i=0;i<maxn;i++)G[i].clear();
	for(int i=0;i<maxn;i++)d[i]=1e9;
	for(int i=0;i<maxn;i++)c[i]=1e9;
	for(int i=0;i<maxn;i++)inq[i]=0;
}
void spfa(int s,int e)
{
	queue<int>q;
	q.push(s);inq[s]=1;d[s]=0;c[s]=0;
	while(!q.empty())
	{
		int now=q.front();
		q.pop(),inq[now]=0;

		//遍历所有边
		for(int i=0;i<G[now].size();i++)
		{
			int v=G[now][i].v;
			//松弛操作
			if(d[v]>d[now]+G[now][i].dis)
			{
				d[v]=d[now]+G[now][i].dis;
				c[v]=c[now]+G[now][i].cos;
				if(inq[v]==1)continue;
				inq[v]=1;
				q.push(v);
			}
		...