随笔 - 87  文章 - 279  trackbacks - 0
<2007年11月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 211616
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

 原来用stl的优先队列这么爽,比赛时候多用,heap太容易打错了,毕竟没ghost_wei那么bt(heap,就几行,都打烂了-_-)

pku3159:

#include <iostream>
#include 
<vector>
#include 
<queue>
using namespace std;

const int INF = 1 << 28;
const int MAXN = 30010;

struct PQNode {
    
int u, key;
    
//pq默认用<判断优先级,key大优先,若要key小优先,则加上!或<改成>即可
    friend bool operator<(const PQNode &a, const PQNode &b) return !(a.key < b.key); } 
    
}
;


int n, m;
vector
<int> adjv[MAXN], adjw[MAXN];

int dijkstraPQ(int st, int en) {
    
int i, v, w, dist[MAXN], chk[MAXN];
    priority_queue
<PQNode> pq;
    PQNode tmp, cp;

    memset(chk, 
0sizeof(chk));
    
for (i=0; i<n; i++) dist[i] = INF;

    dist[st] 
= 0
    tmp.u 
= st; tmp.key = 0;
    pq.push(tmp);
    
while (!pq.empty()) {
        cp 
= pq.top();
        pq.pop();
        
if (cp.u == en) return dist[en];
        
if (chk[cp.u]) continue;
        chk[cp.u] 
= 1;
        
for (i=0; i<adjv[cp.u].size(); i++{
            v 
= adjv[cp.u][i]; w = adjw[cp.u][i];
            
if (!chk[v] && (dist[v]==INF || dist[v]>cp.key+w)) {
                dist[v] 
= cp.key+w;
                tmp.u 
= v; tmp.key = dist[v];
                pq.push(tmp);
            }

        }

    }

    
return -1;
}


int main() {
    
int i, j, k, u, v, w;
    freopen(
"input.txt""r", stdin);
    scanf(
"%d%d"&n, &m);
    
for (i=0; i<m; i++{
        scanf(
"%d%d%d"&u, &v, &w);
        u
--; v--;
        adjv[u].push_back(v);
        adjw[u].push_back(w);
    }

    printf(
"%d\n", dijkstraPQ(0, n-1));
    
return 0;
}


posted on 2007-11-03 16:40 阅读(1304) 评论(4)  编辑 收藏 引用 所属分类: 算法&ACM

FeedBack:
# re: 用stl打spfa短了1k代码,慢了200ms 2007-11-07 20:01 wei
总结了很多ACM ~,牛~,佩服!
有没有资料传我一份,THANKS。。。
邮箱 amyvmiwei@126.com
谢谢!  回复  更多评论
  
# re: 用stl打spfa短了1k代码,慢了200ms 2008-03-31 11:02 AC_Tekkaman
TLE..  回复  更多评论
  
# re: 用stl打spfa短了1k代码,慢了200ms 2009-03-27 22:46 KR
摆明的队列dij。。。。
  回复  更多评论
  
# re: 用stl打spfa短了1k代码,慢了200ms 2010-02-18 02:29 路過
這不是SPFA喔...  回复  更多评论
  

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