syhd142  
日历
<2011年2月>
303112345
6789101112
13141516171819
20212223242526
272812345
6789101112
统计
  • 随笔 - 23
  • 文章 - 122
  • 评论 - 31
  • 引用 - 0

导航

常用链接

留言簿(2)

随笔档案(23)

文章分类(270)

文章档案(122)

我的豆瓣

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
简单图论最短路,要用到priority_queue,好久没用这个了,有点生疏。
#include <stdio.h>
#include 
<string.h>
#include 
<queue>

#define N 20005
#define M 100005
#define INF 1 << 28

struct node
{
    
int id, dis;
    node (){}
    node(
int id, int dis): id(id), dis(dis)
    {
    }
    
bool operator < (const node &it) const
    {
        
return dis > it.dis;
    }
};

struct edge
{
    
int ed, cost;
    edge 
*next;
}
*head[N], table[M];

int pos, dis[N], mk[N];

void Init(int n)
{
    pos 
= 0;
    memset(head, 
0sizeof(head));
}

void Add(int a, int b, int c)
{
    edge 
*= &table[pos++];
    p
->ed = b; p->cost = c;
    p
->next = head[a];
    head[a] 
= p;
}

int Dijkstra(int st, int ed, int n)
{
    
for(int i = 0; i < n; i++)
    {
        mk[i] 
= 0;
        dis[i] 
= INF;
    }
    dis[st] 
= 0;
    std::priority_queue
<node> Q;
    Q.push(node(st, 
0));
    node t;
    
while(!Q.empty())
    {
        t 
= Q.top();
        Q.pop();
        
if(mk[t.id]) continue;
        
if(t.id == ed) return t.dis;
        mk[t.id] 
= 1;
        
for(edge *= head[t.id]; p; p = p->next)
        {
            
if(!mk[p->ed] && p->cost + dis[t.id] < dis[p->ed])
            {
                dis[p
->ed] = p->cost + dis[t.id];
                Q.push(node(p
->ed, dis[p->ed]));
            }
        }
    }
    
return INF;
}

int main()
{
  //  freopen(
"in""r", stdin);
    
int cas = 1;
    
int t, n, m, st, ed;
    scanf(
"%d"&t);
    
while(t--)
    {
        scanf(
"%d %d %d %d"&n, &m, &st, &ed);
        Init(n);
        
for(int i = 0; i < m; i++)
        {
            
int a, b, c;
            scanf(
"%d %d %d"&a, &b, &c);
            Add(a, b, c);
            Add(b, a, c);
        }
        
int ans = Dijkstra(st, ed, n);
        printf(
"Case #%d: ", cas++);
        
if(ans == INF) puts("unreachable");
        
else printf("%d\n", ans);
    }
    
return 0;
}
posted on 2010-09-15 11:21 Fucker 阅读(411) 评论(2)  编辑 收藏 引用 所属分类: ACM/ICPC图论简单
评论:
  • # re: UVA 10986 Sending email  啊啊 Posted @ 2012-10-05 15:58
    你这是spfa吧不是dijstra  回复  更多评论   

  • # re: UVA 10986 Sending email  Fucker Posted @ 2012-10-05 16:47
    明显是dijkstra嘛 @啊啊
      回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


 
Copyright © Fucker Powered by: 博客园 模板提供:沪江博客