Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:wa到不行啊,floyd超时,djkis就是wa,求代码~感激不禁。In Reply To:Re:wa到不行啊,floyd超时,djkis就是wa,求代码~感激不禁。 Posted by:skogt at 2010-08-11 14:35:45 #include<iostream> #include<algorithm> using namespace std; const int MAXN=510; #define inf 0xfffffff int map[MAXN][MAXN]; int f,p,c,m; bool visited[MAXN]; int dis[MAXN]; int main() { int u,v,w; int x; while(scanf("%d%d%d%d",&f,&p,&c,&m)!=EOF) { for(int i=1;i<=f;i++) for(int j=1;j<=f;j++) map[i][j]=inf; while(p--){ scanf("%d%d%d",&u,&v,&w); if(w<map[u][v]) map[u][v]=map[v][u]=w; } int a[110]; for(int i=1;i<=f;i++){ dis[i]=map[1][i]; visited[i]=false; } dis[1]=0; for(int i=1;i<=f;i++){ int min=inf; for(int j=1;j<=f;j++) if(!visited[j] && min>dis[j]) min=dis[x=j]; visited[x]=true; for(int j=1;j<=f;j++) if(!visited[j] && dis[j]>dis[x]+map[x][j]) dis[j]=dis[x]+map[x][j]; } int j=0; int k; for(int i=1;i<=c;i++){ scanf("%d",&k); if(dis[k]<=m) a[j++]=i; } sort(a,a+j); printf("%d\n",j); for(int i=0;i<j;i++) printf("%d\n",a[i]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator