#include <stdio.h>
#include <string.h>

#define N 35
#define MAX_F 1e12
#define MAX_INT 100000000
#define EPS 1e-8
//- an imp of Djstl Alg 
typedef struct City {
	bool isCity;
	char name[20];
	int dist;
} City;

float mat[N][N];
City city[N];

int u[N],mark[N];
float dist[N];

int n;

inline int cmp(float f1, float f2)  {
	if(f1 - f2 > -EPS && f1 - f2 < EPS)
		return 0;
	if(f1 - f2 > EPS)
		return 1;
	return -1;
}

void getSigns(int i1, int i2, float sign)  {
	int i,j;

	memset(u,0,sizeof(u));
	memset(mark,0,sizeof(mark));

	for(i=0;i<n;i++)  {
			dist[i] = mat[i1][i];
	}
	mark[i2] = 1;
	u[i1] = 1;
	float min;
	int mp;
	for(i=0;i<n-1;i++)  {
		min = MAX_F; mp = -1;
		for(j=0;j<n;j++)  {
			if(!u[j] && cmp(dist[j],min) == -1)  {
				min = dist[j];
				mp = j;
			}
		}
		if(mp > -1)  {
			u[mp] = 1; 
			for(j=0;j<n;j++) {
				if(!u[j] && mat[mp][j] + dist[mp] < dist[j])  {
					dist[j] = mat[mp][j] + dist[mp];
					mark[j] = mark[mp];
				}
			}
		}
		else 
			break;
	}
	int numCity= 0,fl;
	for(i=0;i<n;i++)  {
		if(mark[i] && city[i].isCity)  {
			numCity++;
			fl = int(dist[i] - sign);
			if(cmp(dist[i]-sign-fl,0.50f) >= 0) fl ++;
			city[i].dist = fl;
		}

	}
	int sl[N],minI;
	memset(sl,0,sizeof(sl));
	for(i=0;i<numCity;i++)  {
		minI = MAX_INT; mp = -1;
		for(j=0;j<n;j++)  {
			if(mark[j] && city[j].isCity)
				if(!sl[j] && (city[j].dist < minI || 
					city[j].dist == minI && mp >=0 && strcmp(city[j].name,city[mp].name) < 0))  {
					minI = city[j].dist;
					mp = j;
				}
		}
		sl[mp] = 1;
		printf("%-20s%d\n",city[mp].name,city[mp].dist);
	}
}


int main()  {
	int i,j,m,k,a1,a2,idx,s,temp;
	float cost,sign;
	scanf("%d %d %d",&n, &m, &k);
	for(i=0;i<n;i++) for(j=0;j<n;j++) mat[i][j] = MAX_F;
	for(i=0;i<m;i++)  {
		scanf("%d %d %f",&a1, &a2, &cost);
		if(a1 > a2)  {temp = a1; a1 = a2; a2 = temp; }
		mat[a1][a2] = cost;
	}
	for(i=0;i<n;i++)  {
		for(j=0;j<i;j++)  {
			mat[i][j] = mat[j][i];
		}
	}
	for(i=0;i<n;i++) city[i].isCity = false;
	for(i=0;i<k;i++)  {
		scanf("%d",&idx);
		city[idx].isCity = true;
		scanf("%s",city[idx].name);
	}
	scanf("%d",&s);
	for(i=0;i<s;i++)  {
		scanf("%d %d %f",&a1, &a2, &sign);
		getSigns(a1, a2, sign);
		printf("\n");
	}
	scanf("%d",&i);
	return 0;
}

• Re:这题我老是WA，请问有什么陷阱么？？ (23) linkedQueue 2009-03-16 16:12:37
• POJ的测试数据竟然比官网上的还强 (57) sbtdkj1017 2011-11-08 21:28:39
  • Re:POJ的测试数据竟然比官网上的还强 (81) 274856653 2019-04-01 23:06:06