> 在做是，没给Q的大小，所以我做N次单元最短路，存一个二元矩阵。做spfa前，我先按照每个点的权值进行排序，然后显然最大权值的点可以一次SPFA得到即（dis[max][i]=dis1[max][i]+val[amx]），而对于其他点，spfa时，遇到比自己权值大的点，我只如队列一次保证可以通过这个点更新比自己小的点，而比自己小的点则按照正常方法，spfa，为什么总是不过，求大神安慰！！
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define M 1010
int n,m,tot,head[M*2],mark[M],mm[M],Q[M*M];
__int64 dis[M][M];
__int64 oo,kk;
struct node
{
	int to,next;
	__int64 cost;
}edge[M*100];
struct rest
{
	__int64 val;
	int n;
}res[M];
bool cmp(rest a,rest b)
{
	return a.val>b.val;
}
int add(int a,int b,__int64 c)
{
	edge[tot].to=b;edge[tot].cost=c;edge[tot].next=head[a];head[a]=tot++;
	edge[tot].to=a;edge[tot].cost=c;edge[tot].next=head[b];head[b]=tot++;
	return 0;
}
int spfa(int x,__int64 xx)
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		if(!mm[i])
		{
			dis[x][i]=oo;
		}
		mark[i]=0;
	}
	int l,r;
	l=r=0;
	Q[r++]=x;
	mark[x]=1;
	dis[x][x]=xx;
	
	while(l<r)
	{
		int u=Q[l++];
		if(!mm[u])mark[u]=0;//printf("****\n");
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int y=edge[i].to;
			if(mm[y]&&!mark[y])
			{
				dis[x][y]=dis[y][x];
				Q[r++]=y;
				mark[y]=1;
				continue;
			}
			else if(dis[x][u]+edge[i].cost<dis[x][y])
			{
				dis[x][y]=dis[x][u]+edge[i].cost;
				if(!mark[y])Q[r++]=y,mark[y]=1;
			}
		}
	}
	return 0;
}


int main()
{
	int i,j;
	kk=2000000010;
	oo=kk*200100;
	//cout<<oo<<endl;
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0)break;
		for(i=0;i<n;i++)
		{
			res[i].n=i+1;
			scanf("%I64d",&res[i].val);
			//val[i+1]=res[i].val;
		}
		sort(res,res+n,cmp);
		memset(head,-1,sizeof(head));
		memset(mm,0,sizeof(mm));
		int a,b;
		__int64 c;
		tot=0;
		while(m--)
		{
			scanf("%d%d%I64d",&a,&b,&c);
			add(a,b,c);
		}
		for(i=0;i<n;i++)
		{
			
			mm[res[i].n]=1;
			spfa(res[i].n,res[i].val);
			for(j=0;j<i;j++)
			dis[res[i].n][res[j].n]=dis[res[j].n][res[i].n];
		//	printf("**");		
		}
		int pro;
		/*for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			printf("%I64d ",dis[i][j]);
			printf("\n");
		}*/
		scanf("%d",&pro);
		while(pro--)
		{
			scanf("%d%d",&a,&b);
			if(dis[a][b]<oo)printf("%I64d\n",dis[a][b]);
			else printf("-1\n");
		}
		printf("\n");
	}
}
/*
6 7
1 2 3 4 5 6
1 2 1
2 3 2
3 4 3
4 5 4
1 5 5
2 5 2
1 4 3
5
1 4
2 3
1 5
3 5
1 6
2 1
10 20
1 2 5
1
1 2
0 0
*/

• Re:没给Q的大小，所以我做N次单元最短路，存一个二元矩阵，O（n*ke）,过不了，求大神看看联系QQ362697076！！！！ (2518) cl__xy 2012-07-18 16:32:22