哈理工oj 1339Touring解题报告

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1339

这道题是用dijkstra求最短路径，然后找出三个点到一个点的最小路径总和，数据量很大，所以一般朴素的dijkstra会超时，所以采用堆优化，纠结啊，调了一天，最后才想明白怎么处理不可达的情况，这是很多网上给出的堆优化难以解决的问题，也算是学了些东西了。其实学ACM重要的就是这种耐心和灵感。

View Code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<vector>
  5 #define N 5005
  6 using namespace std;
  7 const int NoEdge=0xfffffff;
  8 int size,n;
  9 struct node
 10 {
 11     int n;
 12     int v;
 13 };
 14 node heap[2*N];
 15 int ph[N];
 16 bool used[N];
 17 vector<node> g[N];
 18 int da[N],db[N],dc[N];
 19 int parent(int i)
 20 {
 21     return i>>1;
 22 }
 23 int left(int i)
 24 {
 25     return i<<1;
 26 }
 27 int right(int i)
 28 {
 29     return (i<<1)+1;
 30 }
 31 void MIN_HEAPIFY(int i)//最小根堆
 32 {
 33     node temp;
 34     int small=i;
 35     if(left(i)<=size&&heap[left(i)].v<heap[i].v)
 36     small=left(i);
 37     if(right(i)<=size&&heap[right(i)].v<heap[small].v)
 38     small=right(i);
 39     if(small!=i)
 40     {
 41         ph[heap[small].n]=i;
 42         ph[heap[i].n]=small;
 43         temp=heap[i];
 44         heap[i]=heap[small];
 45         heap[small]=temp;
 46         MIN_HEAPIFY(small);
 47     }
 48 }
 49 node extract_min()//取根节点
 50 {
 51     node min=heap[1];
 52     heap[1]=heap[size--];
 53     ph[heap[1].n]=1;
 54     MIN_HEAPIFY(1);
 55     return min;
 56 }
 57 void decrease(int i,int k)//更新节点的权值
 58 {
 59     heap[i].v=k;
 60     int j;
 61     while(i>1&&heap[i].v<heap[parent(i)].v)
 62     {
 63         ph[heap[parent(i)].n]=i;
 64         ph[heap[i].n]=parent(i);
 65         node temp;
 66         temp=heap[i];
 67         heap[i]=heap[parent(i)];
 68         heap[parent(i)]=temp;
 69         i=parent(i);
 70     }
 71 }
 72 bool empty()
 73 {
 74     return size==0;
 75 }
 76 void dijkstra(int s,int *d)
 77 {
 78     int i,j;
 79     for(i=1;i<=n;i++)
 80     {
 81         heap[i].n=i;
 82         heap[i].v=NoEdge;
 83         ph[i]=i;
 84     }
 85     decrease(s,0);
 86     node min;
 87     while(!empty())
 88     {
 89         min=extract_min();
 90         d[min.n]=min.v;
 91         used[min.n]=true;//已经发现要记住
 92         int num=g[min.n].size();
 93         for(i=0;i<num;i++)
 94         {
 95             if(!used[g[min.n][i].n]&&heap[ph[g[min.n][i].n]].v>min.v+g[min.n][i].v)
 96             {
 97                 decrease(ph[g[min.n][i].n],min.v+g[min.n][i].v);
 98             }
 99         }
100     }
101 }
102 int main()
103 {
104     int i,j;
105     int s,t;
106     int dis;
107     int a,b,c;
108     int m;
109     node temp;
110     int icase=1;
111     while(scanf("%d%d",&n,&m)!=EOF)
112     {
113         memset(used,0,sizeof(used));
114         for(i=1;i<=n;i++)
115         g[i].clear();
116         scanf("%d%d%d",&a,&b,&c);
117         size=n;
118         for(i=1;i<=n;i++)
119         {
120             da[i]=db[i]=dc[i]=NoEdge;
121         }
122         for(i=0;i<m;i++)
123         {
124             scanf("%d%d%d",&s,&t,&dis);
125             temp.n=t;
126             temp.v=dis;
127             g[s].push_back(temp);
128             temp.n=s;
129             g[t].push_back(temp);
130         }
131         printf("Scenario #%d\n",icase++);
132         dijkstra(a,da);
133         if(da[b]==NoEdge||da[c]==NoEdge)
134         {
135             printf("Can not reah!\n\n");
136             continue;
137         }
138         size=n;
139         memset(used,0,sizeof(used));
140         dijkstra(b,db);
141         size=n;
142         memset(used,0,sizeof(used));
143         dijkstra(c,dc);
144         int max=NoEdge;
145         for(i=1;i<=n;i++)
146         {
147             if(da[i]!=NoEdge&&dc[i]+da[i]+db[i]<max)//寻找最小的总权值
148             {
149                 max=dc[i]+da[i]+db[i];
150             }
151         }
152         printf("%d\n\n",max);
153     }
154     return 0;
155 }