xfstart07
Get busy living or get busy dying
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 阅读(24) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理