#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t,p,x,y,m,n,g[1005],f[2][1005][1005],gg[1005];
bool flag[1005];
void doit (int w)
{
	for(int i=1;i<=n;i++)g[i]=f[w][t][i];
	g[t]=0;flag[t]=1;gg[t]=0;
	while(1){
		int p=-1,mm=1000000000;
		for(int i=1;i<=n;i++)if(flag[i]==0&&mm>g[i])p=i,mm=g[i];
		if(p==-1)return;flag[p]=1;gg[p]+=mm;
		for(int i=1;i<=n;i++)if(flag[i]==0&&mm+f[w][p][i]<g[i])g[i]=mm+f[w][p][i];
	}
}
int main ()
{
	scanf("%d%d%d",&n,&m,&t);
	memset(f,64,sizeof(f));
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&p);
        f[0][x][y]=p; f[1][y][x]=p;
    }
    for(int i=0;i<=1;i++){memset(flag,0,sizeof(flag));doit (i);}
    sort(gg+1,gg+n+1);
    printf("%d\n",gg[n]);
}

• Re:orz神犇们的0MS，无任何优化94MS但代码挺短的程序。 (35) xc19881023 2016-04-30 16:52:03