poj 3268 Silver Cow Party 【两次dijstra】

题意:
             就是从各点到X的最短距离及从X到各点的最短距离和的最大值。

第一利用dijstra求出从X到各点的最短距离。

然后所有的边反向,再进行一次dijstra求X到各点的最短路径。

第二次求出的最短路径也就是各点到X的最短路径,因为边已经反向,对于第二次从X到各点的最短路径正是
原图从各点到X的最短路径。

#include<iostream>
#include
<queue>
using namespace std;
const int INF=0x7fffffff/100;
int map[1001][1001]={0};
int d[1001]={0},N,M,X;
int dd[1001]={0};
bool f[1001];
void dijstra()
{
     
for(int i=1; i<=N; i++)
             d[i]
=INF;
     d[X]
=0;
     memset(f,
0,sizeof f);
     
for(int i=1; i<=N; i++)
     {
             
int min=INF,u=0;
             
for(int j=1; j<=N; j++)
                     
if(d[j]<min&&!f[j])
                     {
                                 min
=d[j];
                                 u
=j;
                     }
             f[u]
=true;
             
for(int j=1; j<=N; j++)
             {
                     
if(d[u]+map[u][j]<d[j])
                        d[j]
=d[u]+map[u][j];
             }
     }
     
}

void traverse()
{
     
int temp;
     
for(int i=1; i<=N; i++)
     
for(int j=1; j<i; j++)
     {
             temp 
= map[i][j];
             map[i][j]
=map[j][i];
             map[j][i]
=temp;
     }
}

int main()
{

    cin
>>N>>M>>X;
    
    
for(int i=1; i<=N; i++)
    
for(int j=1; j<=N; j++)
            map[i][j]
=INF;
    
for(int i=1,s,t,value; i<=M; i++)
    {
          cin
>>s>>t>>value;
          map[s][t]
=value;
    }
    
    dijstra();
    
for(int i=1; i<=N; i++)
             dd[i]
=d[i]; 
            
    traverse();
    dijstra();
    
int max=0;
    
for(int i=1; i<=N; i++)
            
if(d[i]+dd[i]>max)max=d[i]+dd[i];
    
    cout
<<max<<endl;
    
    system(
"pause");
    
return 0;
}

posted on 2010-08-19 09:38 田兵 阅读(388) 评论(0)  编辑 收藏 引用 所属分类: 图论题


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


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜