| ||||||||||
| 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