Submission #1001421

---

Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    int N,Q;
    Edge[] e;
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Read();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        long[] circlecosts = new long[N];
        for(int i=0;i<N;i++){
            circlecosts[i] = -1;
        }
        for(int i=0;i<Q;i++){
            if(circlecosts[e[i].a] == -1 || e[i].cost+1 < circlecosts[e[i].a]){
                circlecosts[e[i].a] = e[i].cost + 1;
            }
            if(circlecosts[e[i].b] == -1 || e[i].cost+2 < circlecosts[e[i].b]){
                circlecosts[e[i].b] = e[i].cost + 2;
            }
        }
        for(int i=0;i<N;i++){
            if(i == 0){
                if(circlecosts[N-1] != -1 && (circlecosts[i] == -1 || circlecosts[i] > circlecosts[N-1] + 2)){
                    circlecosts[i] = circlecosts[N-1] + 2;
                }
            }
            else{
                if(circlecosts[i-1] != -1 && (circlecosts[i] == -1 || circlecosts[i] > circlecosts[i-1] + 2)){
                    circlecosts[i] = circlecosts[i-1] + 2;
                }
            }
        }
        for(int i=0;i<N;i++){
            if(i == 0){
                if(circlecosts[N-1] != -1 && (circlecosts[i] == -1 || circlecosts[i] > circlecosts[N-1] + 2)){
                    circlecosts[i] = circlecosts[N-1] + 2;
                }
            }
            else{
                if(circlecosts[i-1] != -1 && (circlecosts[i] == -1 || circlecosts[i] > circlecosts[i-1] + 2)){
                    circlecosts[i] = circlecosts[i-1] + 2;
                }
            }
        }
        for(int i=0;i<N;i++){
            if(i != N-1){
                e[i+Q] = new Edge(i,i+1,circlecosts[i]);
            }
            else{
                e[i+Q] = new Edge(i,0,circlecosts[i]);
            }
        }
        Kruskal K = new Kruskal(N,e);
        sb.Append(K.cost+"\n");
    }
    void Read(){
        string[] str = Console.ReadLine().Split(' ');
        N = int.Parse(str[0]);
        Q = int.Parse(str[1]);
        e = new Edge[Q+N];
        for(int i=0;i<Q;i++){
            str = Console.ReadLine().Split(' ');
            e[i] = new Edge(int.Parse(str[0]),int.Parse(str[1]),Int64.Parse(str[2]));
        }
    }    
}
class UnionFind{
    int[] par;
    public UnionFind(int n){
        par = new int[n];
        for(int i=0;i<n;i++){
            par[i] = i;
        }
    }
    public void Union(int x,int y){
        par[Get(x)] = y; 
    }
    public bool Same(int x,int y){
        return Get(x) == Get(y);
    }
    int Get(int x){
        if(x != par[x]){
            par[x] = Get(par[x]);
        }
        return par[x];
    }
}
class Edge{
    public int a;
    public int b;
    public long cost;
    public Edge(int a0,int b0,long c){
        a = a0;
        b = b0;
        cost = c;
    }
}
class Kruskal{
    int N,M;
    public Edge[] edges;
    public long cost;
    public Kruskal(int n,Edge[] e){
        N = n;
        edges = e;
        M = e.Length;
        Act();
    }
    public Kruskal(int n,int[] a,int[] b,long[] c){
        N = n;
        M = a.Length;
        edges = new Edge[M];
        for(int i=0;i<M;i++){
            edges[i] = new Edge(a[i],b[i],c[i]);
        }
        Act();
    }
    void Act(){
        UnionFind U = new UnionFind(N);
        cost = 0;
        Array.Sort(edges,(a,b) => a.cost > b.cost ? 1 : (a.cost == b.cost ? 0 : -1));
        for(int i=0;i<M;i++){
            if(!U.Same(edges[i].a,edges[i].b)){
                U.Union(edges[i].a,edges[i].b);
                cost += edges[i].cost;
            }
        }
    } 
}

Submission Info

Judge Result