超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC022C解いてみた

ワーシャルフロイド法は初めてでした。

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#define MAX_V 305
#define INF (300*100000*10)
using namespace std;

int N, M;

int d[MAX_V][MAX_V];

typedef pair<int,int> P;

int costs[MAX_V];

int main() {
  for(int i=0;i<MAX_V;++i)
    for(int j=0;j<MAX_V;++j)
      d[i][j] = i == j ? 0 :INF;
  for(int i=0;i<MAX_V;++i)
    costs[i] = INF;
  scanf("%d%d", &N, &M);
  for(int i=0;i<M;++i) {
    int u,v,l;
    scanf("%d%d%d", &u, &v, &l);
    if(u==1||v==1) {
      costs[u-1]=l;
      costs[v-1]=l;
    } else {
      d[u - 1][v - 1] = l;
      d[v - 1][u - 1] = l;
    }
  }
  for(int i=0;i<N;++i) {
    for(int j=0;j<N;++j) {
      for(int k=0;k<N;++k) {
        d[j][k] = min(d[j][k],d[j][i]+d[i][k]);
      }
    }
  }
  int minCost = INF;
  for(int i=1;i<N;++i) {
    for(int j=i+1;j<N;++j) {
      if (costs[i]!=INF && costs[j]!=INF) {
        minCost = min(minCost, costs[i]+costs[j]+d[i][j]);
      }
    }
  }
  if (minCost==INF) {
    printf("-1\n");
  } else {
    printf("%d\n", minCost);
  }
  return 0;
}