dijkstra
#include<iostream>
using namespace std;
int n,s,t,k,m;
int cost[1024][1024];
int dis[1024];
int vis[1024];
int ans;
int dijkstra(int u,int v){
for(int i=1;i<=n;++i){
dis[i]=cost[u][i];
vis[i]=1;
}
dis[u]=0;
vis[u]=0;
for(int i=1;i<n;++i){
int min=0x7FFFFFFF,minj;
for(int j=1;j<=n;++j)
if(vis[j]&&dis[j]<min){
min=dis[j];
minj=j;
}
if(minj==v) return dis[v];
vis[minj]=0;
for(int j=1;j<=n;++j)
if(vis[j]&&dis[j]>dis[minj]+cost[minj][j])
dis[j]=dis[minj]+cost[minj][j];
}
}
int main()
{
char ss[100];
int l;
scanf("%d%d%d%d%d",&n,&s,&t,&k,&m);
gets(ss);
scanf("%d",&l); gets(ss);
memset(cost,127,sizeof(cost));
int x,y,c;
for(int i=1;i<=l;++i){
scanf("%d%d%d",&x,&y,&c);
gets(ss);
if(cost[x][y]>c)
cost[x][y]=c;
}
ans=dijkstra(s,k)+dijkstra(k,t);
if(ans<=m) printf("Yes\n");
else printf("No\n");
printf("%d\n",ans);
return 0;
}
spfa
#include<iostream>
using namespace std;
int n,s,t,k,m,ln;
long long cost[1010][1010];
int lv[1010];
int lw[1010][7010];
long long ans;
int que[1010],head,tail;
long long dis[1010];
int pre[1010];
bool vis[1010];
long long spfa(int u,int v){
for(int i=1;i<=n;++i){
dis[i]=0xFFFFFFF;
pre[i]=i;
vis[i]=1;
}
dis[u]=0;
vis[u]=0;
que[1]=u;
head=tail=1;
while(head<=tail){
int xi=que[(head-1)%n+1],yi;
for(int i=1;i<=lv[xi];++i){
yi=lw[xi][i];
if(dis[yi]>dis[xi]+cost[xi][yi]){
dis[yi]=dis[xi]+cost[xi][yi];
pre[yi]=xi;
if(vis[yi]){
tail++;
que[(tail-1)%n+1]=yi;
vis[yi]=0;
}
}
}
head++;
vis[xi]=1;
}
return dis[v];
}
int main()
{
char ss[100];
scanf("%d%d%d%d%d",&n,&s,&t,&k,&m);
gets(ss);
scanf("%d",&ln); gets(ss);
memset(cost,127,sizeof(cost));
memset(lv,0,sizeof(lv));
int x,y,c;
for(int i=1;i<=ln;++i){
scanf("%d%d%d",&x,&y,&c);
gets(ss);
lv[x]++;
lw[x][lv[x]]=y;
if(cost[x][y]>c)
cost[x][y]=c;
}
ans=spfa(s,k)+spfa(k,t);
if(ans<=m) printf("Yes\n");
else printf("No\n");
printf("%d\n",ans);
return 0;
}
posted on 2009-05-18 00:17
xfstart07 阅读(71)
评论(0) 编辑 收藏 引用