結果
| 問題 |
No.1814 Uribo Road (Easy)
|
| ユーザー |
 watarimaycry2
|
| 提出日時 | 2022-08-11 22:50:45 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,486 bytes |
| コンパイル時間 | 2,711 ms |
| コンパイル使用メモリ | 91,988 KB |
| 実行使用メモリ | 65,512 KB |
| 最終ジャッジ日時 | 2024-09-22 05:34:37 |
| 合計ジャッジ時間 | 12,776 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 6 RE * 38 |
ソースコード
import java.util.*; import java.io.*; import java.math.*;
public class Main{
//見なくていいよ ここから------------------------------------------
static class InputIterator{
ArrayList<String> inputLine = new ArrayList<>(1024);
int index = 0; int max; String read;
InputIterator(){
try{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "UTF-8"));
while((read = br.readLine()) != null){
inputLine.addAll(Arrays.asList(read.split(" ")));
}
}catch(IOException e){}
max = inputLine.size();
}
boolean hasNext(){return (index < max);}
String next(){
if(hasNext()){
return inputLine.get(index++);
}else{
throw new IndexOutOfBoundsException("There is no more input");
}
}
}
static HashMap<Integer, String> CONVSTR = new HashMap<>();
static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
static PrintWriter out = new PrintWriter(System.out);
static void flush(){out.flush();}
static void myout(Object t){out.println(t);}
static void myerr(Object... t){System.err.print("debug:");System.err.println(Arrays.deepToString(t));}
static String next(){return ii.next();}
static boolean hasNext(){return ii.hasNext();}
static int nextInt(){return Integer.parseInt(next());}
static long nextLong(){return Long.parseLong(next());}
static double nextDouble(){return Double.parseDouble(next());}
static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
static ArrayList<String> nextStrArray(int size){
ArrayList<String> ret = new ArrayList<>(size);
for(int i = 0; i < size; i++){
ret.add(next());
}
return ret;
}
static ArrayList<Integer> nextIntArray(int size){
ArrayList<Integer> ret = new ArrayList<>(size);
for(int i = 0; i < size; i++){
ret.add(Integer.parseInt(next()));
}
return ret;
}
static ArrayList<Long> nextLongArray(int size){
ArrayList<Long> ret = new ArrayList<>(size);
for(int i = 0; i < size; i++){
ret.add(Long.parseLong(next()));
}
return ret;
}
@SuppressWarnings("unchecked")
static String myconv(Object list, int no){//only join
StringBuilder sb = new StringBuilder("");
String joinString = CONVSTR.get(no);
if(list instanceof String[]){
return String.join(joinString, (String[])list);
}else if(list instanceof long[]){
long[] tmp = (long[])list;
if(tmp.length == 0){
return "";
}
sb.append(String.valueOf(tmp[0]));
for(int i = 1; i < tmp.length; i++){
sb.append(joinString).append(String.valueOf(tmp[i]));
}
return sb.toString();
}else if(list instanceof int[]){
int[] tmp = (int[])list;
if(tmp.length == 0){
return "";
}
sb.append(String.valueOf(tmp[0]));
for(int i = 1; i < tmp.length; i++){
sb.append(joinString).append(String.valueOf(tmp[i]));
}
return sb.toString();
}else if(list instanceof ArrayList){
ArrayList tmp = (ArrayList)list;
if(tmp.size() == 0){
return "";
}
sb.append(tmp.get(0));
for(int i = 1; i < tmp.size(); i++){
sb.append(joinString).append(tmp.get(i));
}
return sb.toString();
}else{
throw new ClassCastException("Don't join");
}
}
static ArrayList<String> myconv(String str, int no){//only split
String splitString = CONVSTR.get(no);
return new ArrayList<String>(Arrays.asList(str.split(splitString)));
}
static ArrayList<String> myconv(String str, String no){
return new ArrayList<String>(Arrays.asList(str.split(no)));
}
public static void main(String[] args){
CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
solve();flush();
}
//見なくていいよ ここまで------------------------------------------
//このコードをコンパイルするときは、「-encoding UTF-8」を指定すること
static void solve(){//ここがメイン関数
int N = nextInt();
int M = nextInt();
int K = nextInt();
int[][] V = new int[N + 1007][N + 1007];
for(int i = 1; i <= N; i++){
Arrays.fill(V[i], 1000000000);
V[i][i] = 0;
}
ArrayList<Integer> klist = nextIntArray(K);
Collections.sort(klist);
HashMap<Integer, Edge> E = new HashMap<>();
for(int i = 1; i <= M; i++){
int A = nextInt();
int B = nextInt();
int C = nextInt();
V[A][B] = C;
V[B][A] = C;
if(klist.contains(i)){
E.put(i, new Edge(A, B, C));
}
}
String ks = myconv(klist, 0);
for(int k = 1; k <= N; k++){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
V[i][j] = Math.min(V[i][j], V[i][k] + V[k][j]);
}
}
}
int output = 1000000000;
while(!ks.equals("Final")){
for(int i = 0; i < (1 << K); i++){
ArrayList<Edge> select = new ArrayList<>();
for(int j = 0; j < K; j++){
Edge key = E.get(ks.charAt(j) - '0');
if((i & (1 << j)) != 0){
select.add(new Edge(key.A, key.B, key.C));
}else{
select.add(new Edge(key.B, key.A, key.C));
}
}
int sum = 0;
for(int j = 0; j < K; j++){
sum += select.get(j).C;
if(j < K - 1){
sum += V[select.get(j).B][select.get(j + 1).A];
}
}
sum += V[1][select.get(0).A];
sum += V[select.get(K - 1).B][N];
output = Math.min(output, sum);
}
ks = nextPermutation(ks);
}
myout(output);
}
//メソッド追加エリア ここから
static class Edge{
int A;
int B;
int C;
Edge(int A, int B, int C){
this.A = A;
this.B = B;
this.C = C;
}
public String toString(){
return "A : " + A + ", B : " + B;
}
}
static String nextPermutation(String s){
ArrayList<Character> list = new ArrayList<>();
for (int i = 0; i < s.length(); i++) list.add(s.charAt(i));
int pivotPos = -1;
char pivot = 0;
for (int i = list.size() - 2; i >= 0; i--) {
if (list.get(i) < list.get(i + 1)) {
pivotPos = i;
pivot = list.get(i);
break;
}
}
//s is order by asc
if (pivotPos == -1 && pivot == 0) return "Final";
int L = pivotPos + 1;
int R = list.size() - 1;
int minPos = -1;
char min = Character.MAX_VALUE;
for (int i = R; i >= L; i--) {
if (pivot < list.get(i) && list.get(i) < min) {
min = list.get(i);
minPos = i;
}
}
Collections.swap(list, pivotPos, minPos);
Collections.sort(list.subList(L, R+1));
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) sb.append(list.get(i));
return sb.toString();
}
//メソッド追加エリア ここまで
}