Codeforces Beta Round #24
Codeforces Beta Round #24 http://codeforces.com/contest/24
A. Ring road
graphs
ざっくりと大意
・交通渋滞の解消には道路を一方通行にするのが効果的？
・Berland でも取り入れて各地区への経路を一方通行にした。
・全地区回るのに最小のコストはいくらか？
方針のようなもの
・とりあえず移動できるリストみたいなの作って全パターン試せばと思ったら上手く全パターン移動できなかった。。。
・作ってみたリスト
[[0, 0, 0, 0, 4, 16], [0, 0, 23, 15, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 42], [0, 0, 8, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
1番目の地区からは5番目にコスト4で移動、6番目にコスト16で移動できるような感じの。。。。
結局は自力ではAC出せませんでした。。
というのが大幅に解釈が間違っておりました。グラフを図に起こすとこんな感じになりまして、
これを1方向のまわり方で周回できるように道路の向きを変更するのに最小のコストでのような感じです。はい。この図には矢印脇にコスト記入が省略してしまったのですが1-6と2-3の道路の向きを変えると周回できるようになりコストが39ですね。
これを反対周りにする場合は先述の道路以外を全て反転させるのでコストが69かな。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys, io
import re, math
start = time.clock()
"""
def walk(index,tm,l,d,f):
tm+=1
d[index]=tm
print d,f
for i in l[index]:
if not d[i-1]:
tm=walk(i-1,tm,l,d,f)
tm+=1
f[index]=tm
return tm
"""
def main():
n=int(raw_input())
l=[[0 for jc in range(n)] for _ in range(n)]
for a in range(n):
jk=map(int, raw_input().split())
l[jk[0]-1][jk[1]-1]=jk[2]
print l
# print l
ans=0
#スタート地点は毎回1個ずらす
for i in range(len(l)):
sumiko=[]
cost=100000000
ima=i
#終了条件になるまでwhileでぶん回す
while 1:
sumiko.append(ima)
#現在の頂点から移動できる先を探す
for j in range(len(l[i])):
#枝？が全て0なら強制終了
if sum(l[ima])==0:
cost=0
break
#0でなく済リストにもなければ移動処理
if l[ima][j]!= 0 and (j-1) not in sumiko:
# print sumiko,ima
# sumiko.append(ima)
#コストを加算して現在地点を書き換え
cost+=l[ima][j]
ima=j-1
#移動先がなければ終了
break
#探索抜けてきて全周り済ならcostをメモ
if len(sumiko)==n:
ans=min(ans,cost)
print ans
main()
104775のkusanoさんの回答をパクリました。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys, io
import re, math
start = time.clock()
n=int(raw_input())
l=[map(int, raw_input().split()) for _ in range(n)]
#print l
c1=c2=0
p,pr=1,0
for _ in range(n):
for r in l:
if r!=pr:
if r[0]==p:
p=r[1]
c1+=r[2]
pr=r
# print c1
break
if r[1]==p:
p=r[0]
c2+=r[2]
pr=r
# print c2
break
print min(c1,c2)
他の方の回答もいくつも拝見したんですけど移動経路が0or2種類であることが保証されているんだろうか。。
コストの初期値c1,c2が初回に0を代入された以降は加算しか処理がない(っぽい)。。
後でもう少し見直す時間取ろう。。。
追記 01/13/2014 確かに道路の処理の仕方はこれはたとえば図に起こした状態で時計回り、反時計回りの道路ってどんな判定をしているんだろうか。。
