Developing Cities

2 secs 1024 MB

様々な解法がありますが、ここでは Writer 解について述べます。

まず道路の扱いですが、同じ二つの街同士を結ぶ道路に対しては最短距離のもののみを用いた方が有利であることは自明なので、受け取った道路は最短距離のもののみを考えます。
すると、各街同士に最大 $1$ 本までしか道路は存在しないと見なせるので、道路の数は $O(N^2)$ となります。
よって、 Dijkstra 法を用いることで $O(QN^2 \log N)$ 、または $O(QN^2)$ で解くことが出来ます。

以下は計算量に $\log N$ が付かない処理の説明です。
なお、以下で用いる「辺」は「道路」を、「頂点」は「街」を指しています。

一般的に Dijkstra 法を用いる場合は高速化のために優先度付きキューで $O(E \log V)$ で処理するかと思います。もちろん本問題も優先度付きキューを用いて処理してもらっても高速な言語であれば十分高速に処理できます。二頂点間の辺は高々 $1$ 本として扱っているので辺の数は $O(N^2)$ となり、計算量は $O(N^2 \log N)$ となります。

優先度付きキューを用いない方法を考えてみましょう。
$N$ 個の頂点からまだ最短距離が確定していない最小コストの頂点を求めるのに $O(N)$ 、遷移に $O(N)$ 、これを $N$ 回繰り返すので全体として $O(N^2)$ となります。
本問題では $\log N \lt 6$ なので、大きくは変わらないように感じるかもしれませんが、優先度付きキュー自体の定数倍などを考慮すると優先度付きキューを用いない方がより高速に処理できます。
このように、辺の上限が頂点数に対して大きい場合は計算量がより良いアルゴリズムが普段の制約のときと異なる場合があります。

以上より、全体として $O(QN^2)$ で解くことが出来ました。

実装例 ( $O(QN^2)$ 解法 )

C++

xxxxxxxxxx
 
#include <iostream>
#include <climits>
#include <vector>
​
int solve(int n,int x,int y,std::vector<std::vector<int>> &path){
    std::vector<long> ans(n,INT_MAX);
    std::vector<bool> checked(n,false);
    int now;
    long min;
    ans[x] = 0;
    for(int i=0;i<n;++i){
        now = -1;
        min = LONG_MAX;
        for(int j=0;j<n;++j){
            if(!checked[j]&&ans[j]<min){
                now = j;
                min = ans[j];
            }
        }
        checked[now] = true;
        for(int j=0;j<n;++j){
            ans[j] = std::min(ans[j],ans[now]+path[now][j]);
        }
    }
    return ans[y]<INT_MAX?ans[y]:-1;
}
int main(){
    int n,m,q,a,b,c,d,e,f,x,y,t;
    std::cin >> n >> m;
    std::vector<std::vector<int>> path(n,std::vector<int>(n,INT_MAX));
    while(m--){
        std::cin >> a >> b >> c;
        --a;
        --b;
        path[a][b] = std::min(path[a][b],c);
    }
    std::cin >> q;
    while(q--){
        std::cin >> t;
        if(t==1){
            std::cin >> d >> e >> f;
            --d;
            --e;
            path[d][e] = std::min(path[d][e],f);
        }
        else{
            std::cin >> x >> y;
            --x;
            --y;
            std::cout << solve(n,x,y,path) << std::endl;
        }
    }
}

PyPy

xxxxxxxxxx
 
INF = 10**18
​
N,M = map(int,input().split())
cost = [[INF]*N for _ in range(N)]
​
for _ in range(M):
    A,B,C = map(int,input().split())
    A -= 1
    B -= 1
    if C<cost[A][B]:
        cost[A][B] = C
​
Q = int(input())
​
for _ in range(Q):
    
    t,*num = map(int,input().split())
    
    if t==1:
        D,E,F = num
        D -= 1
        E -= 1
        if F<cost[D][E]:
            cost[D][E] = F
        
    else:
        X,Y = num
        X -= 1
        Y -= 1
        ans = [INF]*N
        checked = [False]*N
        ans[X] = 0
        for i in range(N):
            now = -1
            mi = INF
            for j in range(N):
                if not checked[j] and ans[j]<mi:
                    now = j
                    mi = ans[j]
            checked[now] = True
            for j in range(N):
                dist = ans[now]+cost[now][j]
                if dist<ans[j]:
                    ans[j] = dist
        print(ans[Y] if ans[Y]<INF else -1)

Java

xxxxxxxxxx
 
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
        int[][] cost = new int[N][N];
        for(int[] temp:cost)
            Arrays.fill(temp,Integer.MAX_VALUE);
        while(M-->0){
            int A = Integer.parseInt(sc.next())-1;
            int B = Integer.parseInt(sc.next())-1;
            int C = Integer.parseInt(sc.next());
            cost[A][B] = Math.min(cost[A][B],C);
        }
        int Q = Integer.parseInt(sc.next());
        while(Q-->0){
            int t = Integer.parseInt(sc.next());
            if(t==1){
                int D = Integer.parseInt(sc.next())-1;
                int E = Integer.parseInt(sc.next())-1;
                int F = Integer.parseInt(sc.next());
                cost[D][E] = Math.min(cost[D][E],F);
            }
            else{
                int X = Integer.parseInt(sc.next())-1;
                int Y = Integer.parseInt(sc.next())-1;
                System.out.println(solver(N,X,Y,cost));
            }
        }
    }
    private static long solver(int N,int X,int Y,int[][] cost){
        long[] ans = new long[N];
        boolean[] checked = new boolean[N];
        Arrays.fill(ans,Integer.MAX_VALUE);
        ans[X] = 0;
        for(int i=0;i<N;i++){
            int now = -1;
            long min = Long.MAX_VALUE;
            for(int j=0;j<N;j++){
                if(!checked[j]&&ans[j]<min){
                    now = j;
                    min = ans[j];
                }
            }
            checked[now] = true;
            for(int j=0;j<N;j++)
                ans[j] = Math.min(ans[j],ans[now]+cost[now][j]);
        }
        return ans[Y]<Integer.MAX_VALUE?ans[Y]:-1;
    }
}

C

xxxxxxxxxx
 
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
​
int path[50][50];
long ans[50];
bool checked[50];
​
int solve(int n,int x,int y){
    int now,i,j;
    long min,dist;
    for(i=0;i<50;++i){
        ans[i] = INT_MAX;
        checked[i] = false;
    }
    ans[x] = 0;
    for(i=0;i<n;++i){
        now = -1;
        min = LONG_MAX;
        for(j=0;j<n;++j){
            if(!checked[j]&&ans[j]<min){
                now = j;
                min = ans[j];
            }
        }
        checked[now] = true;
        for(j=0;j<n;++j){
            dist = ans[now]+path[now][j];
            if(dist<ans[j]){
                ans[j] = dist;
            }
        }
    }
    return ans[y]<INT_MAX?ans[y]:-1;
}
int main(){
    int n,m,q,a,b,c,d,e,f,x,y,t,i,j;
    scanf("%d %d\n",&n,&m);
    for(i=0;i<50;++i){
        for(j=0;j<50;++j){
            path[i][j] = INT_MAX;
        }
    }
    while(m--){
        scanf("%d %d %d\n",&a,&b,&c);
        --a;
        --b;
        if(c<path[a][b]){
            path[a][b] = c;
        }
    }
    scanf("%d\n",&q);
    while(q--){
        scanf("%d",&t);
        if(t==1){
            scanf("%d %d %d\n",&d,&e,&f);
            --d;
            --e;
            if(f<path[d][e]){
                path[d][e] = f;
            }
        }
        else{
            scanf("%d %d\n",&x,&y);
            --x;
            --y;
            printf("%d\n",solve(n,x,y));
        }
    }
}

C#

xxxxxxxxxx
 
using System;
class Program{
    static void Main(){
        var strs = Console.ReadLine().Split(" ");
        var N = Int32.Parse(strs[0]);
        var M = Int32.Parse(strs[1]);
        var cost = new int[N,N];
        for(var i=0;i<N;i++){
            for(var j=0;j<N;j++){
                cost[i,j] = Int32.MaxValue;
            }
        }
        while(M-->0){
            strs = Console.ReadLine().Split(" ");
            var A = Int32.Parse(strs[0])-1;
            var B = Int32.Parse(strs[1])-1;
            var C = Int32.Parse(strs[2]);
            cost[A,B] = Math.Min(cost[A,B],C);
        }
        var Q = Int32.Parse(Console.ReadLine());
        while(Q-->0){
            strs = Console.ReadLine().Split(" ");
            var t = Int32.Parse(strs[0]);
            if(t==1){
                var D = Int32.Parse(strs[1])-1;
                var E = Int32.Parse(strs[2])-1;
                var F = Int32.Parse(strs[3]);
                cost[D,E] = Math.Min(cost[D,E],F);
            }
            else{
                var X = Int32.Parse(strs[1])-1;
                var Y = Int32.Parse(strs[2])-1;
                Console.WriteLine(Solver(N,X,Y,cost));
            }
        }
    }
    private static long Solver(int N,int X,int Y,int[,] cost){
        var ans = new long[N];
        var check = new bool[N];
        for(var i=0;i<N;i++){
            ans[i] = Int32.MaxValue;
        }
        ans[X] = 0;
        for(var i=0;i<N;i++){
            var now = -1;
            var min = Int64.MaxValue;
            for(var j=0;j<N;j++){
                if(!check[j]&&ans[j]<min){
                    now = j;
                    min = ans[j];
                }
            }
            check[now] = true;
            for(var j=0;j<N;j++)
                ans[j] = Math.Min(ans[j],ans[now]+cost[now,j]);
        }
        return ans[Y]<Int32.MaxValue?ans[Y]:-1;
    }
}

Kotlin

xxxxxxxxxx
 
import kotlin.math.min;
fun main(){
    val(N,M) = readLine()!!.split(" ").map{it.toInt()}
    val path = Array(N, {IntArray(N,{Int.MAX_VALUE})})
    repeat(M){
        val(A,B,C) = readLine()!!.split(" ").map{it.toInt()}
        path[A-1][B-1] = min(path[A-1][B-1],C)
    }
    val Q = readLine()!!.toInt()
    repeat(Q){
        val str = readLine()!!.split(" ");
        if(str[0].toInt()==1){
            val D = str[1].toInt();
            val E = str[2].toInt();
            val F = str[3].toInt();
            path[D-1][E-1] = min(path[D-1][E-1],F)
        }
        else{
            val X = str[1].toInt();
            val Y = str[2].toInt();
            println(solve(N,X-1,Y-1,path))
        }
    }
}
fun solve(N:Int,X:Int,Y:Int,path:Array<IntArray>):Long{
    val ans = LongArray(N,{Int.MAX_VALUE.toLong()})
    val checked = BooleanArray(N)
    ans[X] = 0
    repeat(N){
        var now = -1
        var min = Long.MAX_VALUE
        for(i in 0 until N){
            if(!checked[i]&&ans[i]<min){
                now = i
                min = ans[i]
            }
        }
        checked[now] = true
        for(i in 0 until N){
            ans[i] = min(ans[i],ans[now]+path[now][i])
        }
    }
    return if(ans[Y]<Int.MAX_VALUE) ans[Y] else -1
}

Go

xxxxxxxxxx
 
package main
​
import (
    "bufio"
    "fmt"
    "os"
    "strings"
    "strconv"
    "math"
)
​
func solve(N int,X int,Y int,path [][]int)int{
    ans := make([]int,N)
    checked := make([]bool,N)
    for i:=0;i<N;i++{
        ans[i] = math.MaxInt32
    }
    ans[X] = 0
    for i:=0;i<N;i++{
        num := -1
        min := math.MaxInt64
        for j,val := range ans{
            if !checked[j]&&val<min{
                min = val
                num = j
            }
        }
        checked[num] = true
        for j:=0;j<N;j++{
            dist := ans[num]+path[num][j]
            if dist<ans[j]{
                ans[j] = dist
            }
        }
    }
    if ans[Y]<math.MaxInt32{
        return ans[Y]
    }else{
        return -1
    }
}
​
func main(){
    sc := bufio.NewScanner(os.Stdin)
    sc.Scan()
    strs := strings.Split(sc.Text(), " ")
    N,_ := strconv.Atoi(strs[0])
    M,_ := strconv.Atoi(strs[1])
    path := make([][]int,N)
    for i:=0;i<N;i++{
        path[i] = make([]int,N)
        for j:=0;j<N;j++{
            path[i][j] = math.MaxInt32
        }
    }
    for i:=0;i<M;i++{
        sc.Scan()
        strs = strings.Split(sc.Text(), " ")
        A,_ := strconv.Atoi(strs[0])
        B,_ := strconv.Atoi(strs[1])
        C,_ := strconv.Atoi(strs[2])
        if C<path[A-1][B-1]{
            path[A-1][B-1] = C
        }
    }
    sc.Scan()
    Q,_ := strconv.Atoi(sc.Text())
    for i:=0;i<Q;i++{
        sc.Scan()
        strs = strings.Split(sc.Text(), " ")
        t,_ := strconv.Atoi(strs[0])
        if t==1{
            D,_ := strconv.Atoi(strs[1])
            E,_ := strconv.Atoi(strs[2])
            F,_ := strconv.Atoi(strs[3])
            if F<path[D-1][E-1]{
                path[D-1][E-1] = F
            }
        }else{
            X,_ := strconv.Atoi(strs[1])
            Y,_ := strconv.Atoi(strs[2])
            fmt.Println(solve(N,X-1,Y-1,path))
        }
    }
}

Python(高速化のため少し見辛いです)

xxxxxxxxxx
 
import sys
def main():
    input = sys.stdin.readline
    INF = 10**9
    def solve(N,X,Y,cost):
        ans = INF_LIST[:]
        checked = FALSE_LIST[:]
        ans[X] = 0
        while True:
            mi = INF
            for j, num in enumerate(ans):
                if not checked[j] and num<mi:
                    now = j
                    mi = num
            if mi==INF:
                break;
            checked[now] = True
            num = ans[now]
            subCost = cost[now]
            j = 0
            while j<N:
                dist = num+subCost[j]
                if dist<ans[j]:
                    ans[j] = dist
                j += 1
        print(ans[Y] if ans[Y]<INF else -1)
    N,M = map(int,input().split())
    INF_LIST = [INF]*N
    FALSE_LIST = [False]*N
    cost = [[INF]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = map(int,input().split())
        A -= 1
        B -= 1
        if C<cost[A][B]:
            cost[A][B] = C
    Q = int(input())
    for _ in range(Q):
        t,*num = map(int,input().split())
        if t==1:
            D,E,F = num
            D -= 1
            E -= 1
            if F<cost[D][E]:
                cost[D][E] = F
        else:
            X,Y = num
            X -= 1
            Y -= 1
            solve(N,X,Y,cost)
if __name__ == '__main__':
    main()