[최 단 잡다 한 문제] Codeforces 806 D VK Cup 2017 Round 3 D. Perishable Roads

우 리 는 모든 변 권 을 최소 값 으로 줄 인 후에 하나의 체인 이 분명 하 다 는 것 을 알 게 되 었 습 니 다. 그리고 아래 에 0 변 이 걸 려 있 고 전체 서브 트 리 에 기여 하 는 것 이 0 입 니 다. 그러면 우 리 는 그 체인 을 최소 화 해 야 합 니 다. 우 리 는 이 체인 에 연속 적 인 가중치 가 0 이 라면 a, b, c, d. 그리고 b > c 가 있 으 면 우 리 는 a 를...b. 한 변 으로 바 꾸 면 답 이 더 나 쁘 지 않 고 유일 하 게 안 되 는 것 은 b 는 체인 헤드 가 끝 이 없 으 면 반드시 증가 하 는 것 이다. 그러면 가장 짧 은 길 을 만 들 수 있다.

#include
#include
#include
using namespace std;
typedef long long ll;

const int N=2005;
#define read(x) scanf("%d",&(x))

int n,w[N][N];
ll dis[N];
int vst[N];
int minv;

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(n); minv=1<<30;
  for (int i=1;i<=n;i++)
    for (int j=i+1;j<=n;j++){
      read(w[i][j]); w[j][i]=w[i][j];
      minv=min(minv,w[i][j]);
    }
  for (int i=1;i<=n;i++){
    dis[i]=1LL<<60;
    for (int j=1;j<=n;j++)
      if (i^j){
    w[i][j]-=minv;
    dis[i]=min(dis[i],(ll)w[i][j]<<1);
      }
  }
  for (int i=1;i<=n;i++){
    int k=0;
    for (int j=1;j<=n;j++)
      if (!vst[j] && (!k || dis[j]1;
    for (int j=1;j<=n;j++)
      dis[j]=min(dis[j],dis[k]+w[k][j]);
  }
  for (int i=1;i<=n;i++)
    printf("%I64d
",dis[i]+(ll)(n-1)*minv);
  return 0;
}