uva 10278 - Fire Station

  1 /*
  2  Problem link
  3  Type: Graph - Single source shortest path
  4  Algorithm:
  5      First run Floyd (or Dijkstra to every vertex n), for each vertex
  6      find the distance to the nearest station, get the max of those nearest station.
  7  
  8      For the vertex which is not a station, place a station there and run Dijkstra
  9      for that vertex. Recalculate the distance to the nearest station for each vertex
 10      by the distance array from the Dijkstra and update the for the "better max".
 11  */
 12  #include <iostream>
 13  #include <cstdio>
 14  #include <cstdlib>
 15  #include <cstring>
 16  #include <cmath>
 17  #include <vector>
 18  #include <queue>
 19  #include <algorithm>
 20  using namespace std;
 21  
 22  const int maxn = 510;
 23  const int oo = 100000000;
 24  
 25  bool isStation[maxn], visited[maxn];
 26  int d[maxn][maxn];
 27  int start[maxn],end[maxn],dist[maxn],nearest[maxn],tmp[maxn];
 28  
 29  class Edge
 30  {
 31  public:
 32      int a,b,t;
 33  
 34      Edge() {}
 35  
 36      Edge(int aa, int bb, int tt): a(aa), b(bb), t(tt) {}
 37  
 38      bool operator<(const Edge& E) const { return (this->a<E.a); }
 39      bool operator>(const Edge& E) const { return (this->a>=E.a); }
 40  };
 41  
 42  class Vertex
 43  {
 44  public:
 45      int v;
 46  
 47      Vertex() {}
 48      Vertex(int vv): v(vv) {}
 49  
 50      bool operator<(const Vertex& V) const { return (dist[this->v]<dist[V.v]); }
 51      bool operator>(const Vertex& V) const { return (dist[this->v]>=dist[V.v]);}
 52  };
 53  
 54  vector<Edge> Elist;
 55  priority_queue<Vertex, vector<Vertex>, greater<Vertex> > pq;
 56  int n,f;
 57  
 58  void readfile();
 59  void Dijkstra(int s);
 60  int process();
 61  
 62  int main()
 63  {
 64      int ntest;
 65      string str;
 66      cin >> ntest;
 67      for (int test=1; test<=ntest; test++)
 68      {
 69          readfile();
 70          if (test>1) cout << endl;
 71          sort(Elist.begin(), Elist.end(), less<Edge>());
 72          start[Elist[0].a] = 0;
 73          for (unsigned int i=1; i<Elist.size(); i++)
 74              if (Elist[i].a!=Elist[i-1].a)
 75              {
 76                  end[Elist[i-1].a] = i-1;
 77                  start[Elist[i].a] = i;
 78              }
 79          end[Elist[Elist.size()-1].a] = Elist.size()-1;
 80          cout << process() << endl;
 81          Elist.clear();
 82      }
 83      return 0;
 84  }
 85  
 86  void readfile()
 87  {
 88      cin >> f >> n;
 89      for (int i=1; i<=n; i++)
 90          for (int j=1; j<=n; j++) d[i][j] = oo;
 91      for (int i=0; i<=n; i++)
 92      {
 93          isStation[i] = false;
 94          nearest[i] = oo;
 95          d[i][i] = 0;
 96      }
 97      int value;
 98      for (int i=1; i<=f; i++)
 99      {
100          cin >> value;
101          isStation[value] = true;
102          nearest[value] = 0;
103      }
104      string line;
105      getline(cin,line);
106      while (true)
107      {
108          getline(cin,line);
109          if (line=="" || cin.eof()) break;
110          int value[3] = {0,0,0}, j = 0;
111          for (unsigned int i=0; i<line.length(); i++)
112              if (line[i]==' ') j++;
113              else value[j] = value[j]*10+int(line[i])-48;
114          Elist.push_back(Edge((value[0]),(value[1]),(value[2])));
115          Elist.push_back(Edge((value[1]),(value[0]),(value[2])));
116          d[value[0]][value[1]] = value[2];
117          d[value[1]][value[0]] = value[2];
118      }
119  }
120  
121  void Dijkstra(int s)
122  {
123      for (int i=1; i<=n; i++)
124      {
125          dist[i] = +oo;
126          visited[i] = false;
127      }
128      dist[s] = 0;
129      visited[s] = true;
130      pq.push(Vertex(s));
131  
132      while(!pq.empty())
133      {
134          int u = pq.top().v; pq.pop();
135          visited[u] = true;
136          for (int i = start[u]; i<=end[u]; i++)
137          {
138              int v = Elist[i].b;
139              if (!visited[v] && dist[v]>dist[u]+Elist[i].t)
140              {
141                  dist[v] = dist[u]+Elist[i].t;
142                  pq.push(Vertex(v));
143              }
144          }
145      }
146  }
147  
148  int process()
149  {
150      int result = 1,
151          maxlen = 0,
152          minlen = oo;
153  
154      //Floyd
155      for (int k=1; k<=n; k++)
156          for (int i=1; i<=n; i++)
157              for (int j=1; j<=n; j++)
158                  if (d[i][j]>d[i][k]+d[k][j]) d[i][j] = d[i][k]+d[k][j];
159  
160      //Calculate nearest
161      for (int i=1; i<=n; i++)
162          if (!isStation[i])
163          {
164              for (int j=1; j<=n; j++)
165                  if (isStation[j] && d[i][j]<nearest[i]) nearest[i] = d[i][j];
166              if (nearest[i]>maxlen) maxlen = nearest[i];
167          }
168  
169      minlen = maxlen;
170      for (int i=1; i<=n; i++)
171          if (!isStation[i])
172          {
173              isStation[i] = true;
174              Dijkstra(i);    // Run Dijkstra
175              maxlen = 0;
176              for (int j=1; j<=n; j++) tmp[j] = nearest[j];
177              tmp[i] = 0;
178              for (int j=1; j<=n; j++)
179                  if (!isStation[j] && dist[j]<tmp[j]) tmp[j] = dist[j]; // update nearest
180              for (int j=1; j<=n; j++)
181                  if (tmp[j]>maxlen) maxlen = tmp[j];
182              if (maxlen<minlen)  // update better max
183              {
184                  result = i;
185                  minlen = maxlen;
186              }
187              isStation[i] = false;
188          }
189      return(result);
190  }