T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
http://acm.pku.cn/JudgeOnline/problem?id=3159
求最短路Dij,数据太强了
 1/********************************
 2Source Code
 3
 4Problem: 3159  User: Torres 
 5Memory: 3328K  Time: 1422MS 
 6Language: C++  Result: Accepted 
 7********************************/

 8#include<iostream>
 9#include<vector>
10#include<algorithm>
11#include<queue>
12using namespace std;
13
14const int Nmax=30005;
15const int oo=0x7fffffff;
16
17typedef struct node{
18    int end,len;
19    node(int a=0,int b=oo):end(a),len(b){};
20    bool operator<(const node &a)const{
21        return this->len>a.len;
22    }

23}
node;
24
25vector<vector<node> >dist(Nmax);
26bool used[Nmax];
27int N,M,i,j;
28
29int Dijkstra(int s,int e)
30{
31    vector<int>closed(N+1,oo);
32    bool used[Nmax]={false};
33    priority_queue<node>q;
34    q.push(node(s,0));
35    closed[s]=0;
36    while(!q.empty()){
37        node ntemp=q.top();
38        q.pop();
39        if(used[ntemp.end])continue;
40        if(ntemp.end==e)return ntemp.len;
41        used[ntemp.end]=true;
42
43        int sz=dist[ntemp.end].size();
44        for(j=0;j<sz;j++){
45            int en=dist[ntemp.end][j].end;
46            int le=ntemp.len+dist[ntemp.end][j].len;
47            if(!used[en]&&le<closed[en]){
48                closed[en]=le;
49                q.push(node(en,le));
50            }

51        }

52        
53    }

54    return closed[e];
55}

56
57int main()
58{
59    int s,e,l;
60    scanf("%d%d",&N,&M);
61    for(i=1;i<=M;i++){
62        scanf("%d%d%d",&s,&e,&l);
63        dist[s].push_back(node(e,l));
64    }

65    printf("%d\n",Dijkstra(1,N));
66    return 0;
67}

68
69

以后用vector定义二维数组用vector<vector<> >v吧,不要vector<>v[]。
posted on 2008-09-02 19:19 Torres 阅读(588) 评论(0)  编辑 收藏 引用 所属分类: Graph

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