최 단 경로 - Dijkstra (poj 1135)

제목:
 도미 노 골패 게임 이 있 습 니 다. 우 리 는 관건 적 인 골패 와 일반 골패 가 있다 는 것 을 알 고 있 습 니 다. 관건 적 인 골패 를 넘 어 뜨 린 후에 전체 골패 진 이 쓰 러 지고 다른 관건 적 인 골패 를 추진 합 니 다. 그 중에서 관건 적 인 골패 A 를 넘 어 뜨리 는 관건 적 인 골패 B 도 넘 어 지고 일정한 시간 이 필요 합 니 다. 그래서 본 문 제 는 마지막 으로 넘 어 진 골패 의 위 치 를 구 해 야 합 니 다.그 시간 과...
분석:
마지막 에 쓰 러 진 패 는 두 가지 상황 이 있다.
① 마지막 에 쓰 러 진 카드 가 관건 적 인 카드 라면 그 시간 과 위 치 는 첫 번 째 관건 적 인 카드 에서 다른 관건 적 인 카드 에서 짧 은 경로 의 최대 치 와 대응 하 는 관건 적 인 카드 이다.
② 마지막 에 쓰 러 진 카드 가 두 장의 관건 적 인 카드 사이 의 특정한 일반 카드 라면 그 시간 은 이 줄 의 두 개의 관건 적 인 골패 에서 1 골패 의 가장 짧 은 시간 에 이 줄 의 시간 을 더 해 2 로 나 누고 위 치 는 이 두 장의 관건 적 인 카드 사이 의 특정한 일반 카드 이다.
그래서 실질 적 으로 가장 짧 은 길 + 매 거 진;
주:
10 조 의 데 이 터 를 조심 하 세 요.이 데이터 의 유효 출력 은 0.0s 가 1 위치 에 있 을 것 입 니 다.
코드:

#include <queue>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
using namespace std;
const int MAX_N = 510;
const int MAX = 1 << 30;
int map[MAX_N][MAX_N];
int dist[MAX_N];
int N, M;

struct cmp{
  bool operator()(int a, int b)
  {
    return dist[a] > dist[b];
  }
};

priority_queue<int, vector<int>, cmp> Q;

void Dijkstra(int start)
{
  for(size_t i = 1; i <= N; ++i)
    dist[i] =MAX;
  Q.push(start);
  dist[start] = 0;
  while(!Q.empty())
  {
    int idx = Q.top();
    Q.pop();
    for(size_t i = 1; i <= N; ++i)
    {
      if((dist[idx] + map[idx][i]) < dist[i])
      {
        Q.push(i);
        dist[i] = dist[idx] + map[idx][i];
      }
    }
  }
}
int main()
{
  int cnt = 1;
  while( cin >> N >> M)
  {
    if(N == 0 && M == 0)
      break;
    for(size_t i = 0; i <= N; ++i)
      for(size_t j = 0; j <= N ; ++j)
        map[i][j] = MAX;
    for(size_t i = 1; i <= N; ++i)
      map[i][i] = 0;
    for(size_t i = 0; i < M; ++i)
    {
      int u, v, cost;
      cin >> u >> v >> cost;
      map[u][v] = cost;
      map[v][u] = cost;
    }
    Dijkstra(1);
    double res = -1.0f;
    int idx1, idx2, idx3;
    idx1 = 1;
    for(size_t i = 1; i <=N; ++i)
    {
      if(dist[i] > res)
      {
        res = dist[i];
        idx1 = i;
      }
    }
    double tmp;
    idx2 = -1;
    for(size_t i = 1; i <=N; ++i)
      for(size_t j = i + 1; j <= N ;++j)
      {
        if(map[i][j] != MAX)
        {
          tmp = (dist[i] + dist[j] + map[i][j]) / 2.0f;
          if(tmp > res)
          {
            res = tmp;
            idx2 = i;
            idx3 = j;
          }
            
        }
      }
    cout << "System #" << cnt << endl;
    if(idx2 == -1)
      printf("The last domino falls after %.1f seconds, at key domino %d.

",res, idx1);
    else 
      printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.

", res, idx2, idx3);
    cnt++;
  }
}