T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks

http://acm.hust.edu.cn/thx/problem.php?id=1163
今天做了一个题,郁闷了一下午,vector又忘记clear了,~~~5555,是一个dij,求最短路的最大距离,我用vector模拟了一个邻接表,因为v的数目达到了10000,矩阵是不行的。但却每每在最后忘了clear,多case啊。。。。
不过dij的速度慢的很,以后注意,教训!

 1/****************************************************************
 2    Problem: 1163
 3    User: Torres
 4    Language: C++
 5    Result: Accepted
 6    Time:1448 ms
 7    Memory:1480 kb
 8****************************************************************/

 9
10#include<iostream>
11#include<vector>
12#include<algorithm>
13using namespace std;
14#define Nmax 10005
15const int oo=0x7fffffff;
16template<class T>void print(T *a,int n){for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl;}
17
18typedef struct node{
19    int end,value;
20    node(int a=0,int b=oo){
21        end=a;
22        value=b;
23    }

24}
node;
25
26vector<node> dist[Nmax];
27int closed[Nmax];
28bool used[Nmax];
29
30int main()
31{
32    int T,ca,P,C,x,y,dis1,dis2;
33    int i,j,k;
34    node temp;
35    int m,re;
36    scanf("%d",&T);
37    for(ca=1;ca<=T;ca++){
38        scanf("%d%d",&P,&C);
39        for(i=0;i<P;i++)
40            scanf("%d",&closed[i]);
41        for(i=1;i<=C;i++){
42            scanf("%d%d%d%d",&x,&y,&dis1,&dis2);
43            temp.end=y;
44            temp.value=dis1;
45            dist[x].push_back(temp);
46            temp.end=x;
47            temp.value=dis2;
48            dist[y].push_back(temp);
49        }

50        memset(used,false,sizeof(used));
51        for(i=1;i<P;i++){
52            int min=oo;
53            int itemp;
54            for(k=0;k<P;k++)
55                if(!used[k]&&closed[k]<min){
56                    min=closed[k];
57                    itemp=k;
58                }

59            used[itemp]=true;
60            int sz=dist[itemp].size();
61            for(k=0;k<sz;k++){
62                j=dist[itemp][k].end;
63                int v=dist[itemp][k].value;
64                if(!used[j]&&closed[j]>closed[itemp]+v)
65                    closed[j]=closed[itemp]+v;
66            }

67        }

68        m=closed[0];re=0;
69        for(i=0;i<P;i++)
70            if(closed[i]>m){
71                m=closed[i];
72                re=i;
73            }

74        printf("Scenario #%d:\n%d\n\n",ca,re);
75        for(i=0;i<Nmax;i++) dist[i].clear();
76    }

77    return 0;
78}

79
posted on 2008-08-29 20:06 Torres 阅读(240) 评论(1)  编辑 收藏 引用 所属分类: Graph

评论

# re: HUST 1163 2008-10-22 20:17
加油哈
BEIJING  回复  更多评论
  


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