TOI 2008 4. 地道問題
作法 : SPFA
大概2秒多...算了
測資的點跟敘述不一樣啊 只開10001個!
/********************************************************/
#include<stdlib.h>
#include<stdio.h>
#define MAX 1000000001
long long int min(long long int x,long long int y)
{
if(x>=y) return y;
else return x;
}
long long int input()
{
char cha;
long long int x=0;
while(cha=getchar())
if(cha!=' '&&cha!='\n') break;
x=cha-48;
while(cha=getchar())
{
if(cha==' '||cha=='\n') break;
x=x*10+cha-48;
}
return x;
}
int ptime[10002]={0},SP[10002]={0};
long long int data[1000000][3],SUM;
short Queue[5000000];
int SPFA(int S,int N)
{
long long int Dis[10002]={0};
int top=-1,a,b,c,used[10002]={0};
for(a=1;a<=N;a++)
Dis[a]=MAX;
for(a=SP[S],b=0;b<ptime[S];a++,b++)
{
Dis[data[a][1]]=min(Dis[data[a][1]],data[a][2]);
if(used[data[a][1]]==0)
Queue[++top]=data[a][1],used[data[a][1]]=1;
}
Dis[S]=0;
for(a=0;a<=top;a++)
{
int Qp=Queue[a];
used[Qp]=0;
for(b=SP[Qp],c=0;c<ptime[Qp];b++,c++)
if(Dis[data[b][1]]>Dis[Qp]+data[b][2])
{
Dis[data[b][1]]=Dis[Qp]+data[b][2];
if(used[data[b][1]]==0)
Queue[++top]=data[b][1],used[data[b][1]]=1;
}
}
if(S==1)
for(a=2;a<=N;a++)
SUM+=Dis[a];
else
SUM+=Dis[1];
return 0;
}
int partition(int, int);
void quicksort(int, int);
main()
{
int N,M;
while(scanf("%d %d",&M,&N)==2)
{
int a,b,c,d,x,y;
for(a=0;a<N;a++)
{
x=input(),y=input(),d=input();
data[a][0]=x,data[a][1]=y,data[a][2]=d;
ptime[x]++;
}
quicksort(0,N-1);
for(a=1;a<=M;a++)
SP[a]=MAX;
for(a=0;a<N;a++)
SP[data[a][0]]=min(a,SP[data[a][0]]);
SUM=0;
int Flag=0;
for(a=1;a<=M;a++)
Flag=SPFA(a,M);
printf("%lld\n",SUM);
for(a=1;a<=M;a++)
ptime[a]=0;
}
return 0;
}
int partition(int left,int right)
{
int a=left-1,b,s=data[right][0];
for(b=left;b<right;b++)
{
if(data[b][0]<s)
{
a++;
long long int temp;
temp=data[a][0];
data[a][0]=data[b][0];
data[b][0]=temp;
temp=data[a][1];
data[a][1]=data[b][1];
data[b][1]=temp;
temp=data[a][2];
data[a][2]=data[b][2];
data[b][2]=temp;
}
}
long long int temp;
temp=data[a+1][0];
data[a+1][0]=data[right][0];
data[right][0]=temp;
temp=data[a+1][1];
data[a+1][1]=data[right][1];
data[right][1]=temp;
temp=data[a+1][2];
data[a+1][2]=data[right][2];
data[right][2]=temp;
return a+1;
}
void quicksort(int left,int right)
{
int q;
if(left<right)
{
q=partition(left,right);
quicksort(left,q-1);
quicksort(q+1,right);
}
}