注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

图论_Dijkstra算法_poj3268  

2011-08-14 23:33:44|  分类: ACM_图论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
通过这个题目学习Dijkstra算法
题目描述:(直接ctrl + C 的discuss里的 :P)
一只母牛从N块田中的任一块(1≤N≤1000)去参加盛大的母牛聚会,这个聚会被安排在X号田(1≤X ≤N)。一共有M(1 ≤ M ≤ 100,000)条单行道分别连接着两块田,且通过路i需要花Ti(1≤Ti≤100)的时间。 每头母牛必需参加宴会并且在宴会结束时回到自己的领地,但是每头牛都很懒而喜欢选择化是最少的一个方案。来时的路和去时的可能不一样。 求每头牛要来回的最短时间。 输入
第一行:三个用空格分开的整数:N,M和X 第2到第M+1行:第i+1描述路i,通过三个用空格分开的整数: Ai, Bi和Ti. 是对于从Ai号田到 Bi号田的描述,需要Ti的时间.  输出  第一行:一个整数:对于每头牛所必须花费的时间.(在这段时间内,每头牛可以来回)

分析:求两次的最短路就行了,从x走到每个母牛个子的田里好说,直接dijkstra,怎么算从每个母牛的田里走到x的最短路?
网上某个大牛提供了一种逆向思考的解决方法:把所有的边反向,再进行一次dijkstra求x到各点的最短路径,
第二次求出的最短路径也就是各点到X的最短路径,因为边已经反向,对于第二次从X到各点的最短路径正是
原图从各点到X的最短路径。

代码:
1)dijkstra + 邻接矩阵 O(n^2) 
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,x;
const int MAXN = 1010;
const int MAXD = 0x7ffffff; //小心这个不能太大,否则就溢出了!!
int cost[MAXN][MAXN]; //邻接矩阵
int dis[MAXN];//从x到其他点的最短距离
bool ins[MAXN];// 如果到这个点的最短距离已经求出来了,ins值为true

void init()
{
       int i;
       int j;
       int a,b,t;
       scanf("%d %d %d",&n,&m,&x);
       for(i = 1;i <= n;i ++)
              for(j = 1;j <= n;j ++)
                     cost[i][j] = MAXD;
       for(i = 1;i <= m;i ++)
       {
              scanf("%d %d %d",&a,&b,&t);
              cost[a][b] = t;       
       }       
}
int max(int x,int y)
{
       return ( x > y) ? x:y;
}
void dijkstra()
{
       int i,j;
       for(i = 1;i <= n;i ++)
       {
              dis[i] = MAXD; //初始化距离
              ins[i] = false;   
       }
       dis[x] = 0;
       ins[x] = true;
       int pre = x;
       int t;
       int min;
       for(i = 1;i <= n-1;i ++)
       {
              for(j = 1;j <= n;j ++)
              {
                     t = dis[pre] + cost[pre][j];
                     if(t < dis[j] && !ins[j])
                     {
                            dis[j] = t;
                     }
              }
              min  = MAXD;
              for(j = 1;j <= n;j ++)// 求出下一个pre,pre表示在已经求出最短距离的点中,距离最小的点
              {
                     if(min > dis[j] && !ins[j])
                     {
                            pre = j;
                            min = dis[j];       
                     }       
              }
              ins[pre] = true; // 
       }       
}
void tranverse() // 转置矩阵
{
       int i,j;
       int t;
       for(i = 1;i <= n;i ++)
       {
              for(j = i;j <= n;j ++)
              {
                     t = cost[i][j];       
                     cost[i][j]  = cost[j][i];
                     cost[j][i] = t;
              }
       }
}
void work()
{
       int i;
       int maxx = -1;
       int ans ;
       int d[MAXN];
       dijkstra();
       for(i = 1;i <= n;i ++)
       {
              d[i] = dis[i];
       }
              
       tranverse();
       dijkstra();
       for(i = 1;i <= n;i ++)
       {
              maxx = max(dis[i]+d[i],maxx);
       }
       ans = maxx;
       printf("%d\n",ans);
}
int main()
{
       init();
       work();
       return 0;
}
2)priority_queue + dijsktra +邻接矩阵

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x7ffffff; //距离的最大值
const int MAXN = 1010; //点的最大个数
typedef pair<int,int> ele; //在priority_queue中会用到
int edge[MAXN][MAXN]; //边 权值
int dis[MAXN]; //到这个点的最小距离
int n,m,x; 
bool S[MAXN]; //集合S,表示对应算法导论中的S
void init()
{
        int i,j;
        int a,b,t;
        scanf("%d %d %d",&n,&m,&x);
        for(i = 1;i <= n;i ++)
                dis[i] = INF;
        for(i = 1;i <= n;i ++)
                for(j = 1;j <= n;j ++)
                        edge[i][j] = INF;
        for(i = 1;i <= m;i ++)
        {
                scanf("%d %d %d",&a,&b,&t);
                edge[a][b] = t;
        } 
}
void dijkstra()
{
        int i;
        for(i = 1;i <= n;i ++)
        {
                dis[i] = INF;//初始化dis
                S[i] = false;//初始化S
        }        
        dis[x] = 0;
//        S[x] = true;//注意这里
        ele pre;
        int  td;
        priority_queue<ele,vector<ele>,greater<ele> >col;//greater 从小到达
        col.push(make_pair(dis[x],x));//根据dis【】来确定优先级
        while(!col.empty())
        {
                pre = col.top();
                col.pop();
                if(S[pre.second])//这里是必要的,因为在下面for循环的时候,可能插入已经在col中的点
                        continue;
                S[pre.second] = true;
                for(i = 1;i <= n;i ++)        
                {
                        td = dis[pre.second] + edge[pre.second][i];        
                        if(td < dis[i] && !S[i] )
                        {
                                dis[i] = td;
                                col.push(make_pair(dis[i],i));
                        }
                }
        }        
}
void tranverse()
{
        int i,j;
        int t;
        for(i = 1;i <= n;i ++)
        {
                for(j = i;j <= n;j ++)
                {
                        t = edge[i][j];
                        edge[i][j] = edge[j][i];
                        edge[j][i] = t;                        
                }
        }
}
int max(int x,int y)
{
        return (x > y ) ? x : y;
}
void work()
{
        int i;
        int d[MAXN] ;
        int ans = -1;
        dijkstra();        
        for(i = 1;i <= n;i ++)        
        {
                d[i] = dis[i];
        }
        tranverse();
        dijkstra();
        for(i = 1;i <= n;i ++)
        {
                ans = max(ans,d[i] + dis[i]);
        }        
        printf("%d\n",ans);
}
int main()
{
        init();
        work();
        return 0;
}

  评论这张
 
阅读(139)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018