参考になったダイクストラ法
from heapq import heappush, heappop
import math
INF = 10 ** 18
def dijkstra(s, n): # (始点, ノード数)
dist = [INF] * n
hq = [(0, s)] # (distance, node)
dist[s] = 0
seen = [False] * n # ノードが確定済みかどうか
while hq:
v = heappop(hq)[1] # ノードを pop する
if seen[v]:
continue
seen[v] = True
for to, cost, k in adj[v]: # ノード v に隣接しているノードに対して
if seen[to] == False and math.ceil(dist[v]/k)*k + cost < dist[to]:
dist[to] = cost + math.ceil(dist[v]/k)*k
heappush(hq, (dist[to], to))
return dist
N,M,X,Y=map(int,input().split())
adj = [[] for _ in range(N)]
for i in range(M):
a, b, t, k = map(int, input().split())
adj[a-1].append*1
adj[b-1].append*2
L=dijkstra(X-1,N)
if L[Y-1]==INF:
print(-1)
else:
print(L[Y-1])
ダイクストラ法クラスで！
予めEdgeデータとdis(コスト)を用意してあげる必要があります。
import heapq
V,E,r = map(int,input().split())
dis = [[float('inf')]*V for _ in range(V)]
Edge = [[] for _ in range(V)]
for _ in range(E):
s,t,d = map(int,input().split())
dis[s][t] = d
Edge[s].append(t)
class Diac:#(start,number of ver)-> distance
def __init__(self,r,V):#rはスタート地点
self.long = [float('inf') for _ in range(V)]#経路保存用
self.long[r] = 0
def diac(self):
self.q = [(0,r)]#そこまでの最短距離、頂点
while self.q:
self.div,self.v = heapq.heappop(self.q)#最短距離とその頂点を取り出す,tuppleでははじめの要素の最小値から
for next in Edge[self.v]:
if self.long[self.v] + dis[self.v][next] < self.long[next]:
self.long[next] = self.long[self.v] + dis[self.v][next]
heapq.heappush(self.q,(self.long[next],next))
return self.long
X = Diac(r,V)
for i in X.diac():
if i == float('inf'):
print('INF')
continue
print(i)
Atcoder come back quicklyをサンプルだけとけるやつ
classでDFSを使って見たのですがReになってしまいました。（サンプルはいけた）
結構更新の考え方に慣れてきてよかったなあと思ったのですが肝心のところでTLEやREが取れない。。なお回答はダイクストラ法だったので頑張って習得します。（今週中）
Reの部分は再帰関数のリミットによるもので書き換え可能だそうです。
N,M = map(int,input().split())
cost = [[float('inf')] * N for _ in range(N)]
edge = [[] for _ in range(N)]
for _ in range(M):
a,b,c = map(int,input().split())
if cost[a-1][b-1] > c:
cost[a-1][b-1] = c
if b-1 not in edge[a-1]:
edge[a-1].append(b-1)
class DFS:
def __init__(self,st):
self.ans = float('inf')
self.seen = [0 for _ in range(N)]
self.st = st
self.res = []
self.circle = False
def dfs(self,now,dis):
self.seen[now] += 1
if edge[now] == []:
return
if self.seen[now] > 1:
return
for next in edge[now]:
if next == self.st:
if self.ans > dis + cost[now][next]:
self.ans = dis + cost[now][next]
self.res.append(self.ans)
self.circle = True
else:
self.dfs(next,dis + cost[now][next])
self.seen[next] -=1
if self.circle:
return min(self.res)
else:
return -1
for i in range(N):
X = DFS(i)
print(X.dfs(i,0))
pythonで機械学習用学習データ作成GUIをつくる！-2
# coding=utf-8
from tkinter import filedialog
from PIL import Image
import matplotlib.pyplot as plt
import os
fld = filedialog.askdirectory()
file_path = []#include file_path in appointed directory
for curDir, dirs, files in os.walk(fld):
for file in files:
file_path.append(os.path.join(curDir, file))
new_dir = os.getcwd() + r'\triminged_image'#created new directory
os.makedirs(new_dir,exist_ok=True)
img_pathes = []
print(file_path)
for j in range(len(file_path)):
img_path = new_dir + r'\sample{}.jpg'.format(j)
print(img_path)
img_pathes.append(img_path)
img = Image.open(file_path[j])
img.save(img_path)
import Main_GUI
Main_GUI.gui(img_pathes)
Tkinterで作ろうとして挫折しましたが、triminged_imageファイルを新しく作ってその中に参照した画像を入れるところまではいけました！
GUIをモジュールとして読み込んで渡そうと思っています！
pythonで機械学習用学習データ作成GUIをつくる！-1
まず実行フォルダと同じディレクトリに読み込んだファイルの0番目の画像を、新規ディレクトリ内に保存するコードを書きました！
filedialogで選択する画像ディレクトリをゲットします。
次にそれらの画像のファイルパスをゲットし、インデックス番号に応じた名前で画像を新しく作成したディレクトリに保存するものです！
# coding=utf-8
from tkinter import filedialog
from PIL import Image
import matplotlib.pyplot as plt
import os
fld = filedialog.askdirectory()
file_path = []#include file_path in appointed directory
for curDir, dirs, files in os.walk(fld):
for file in files:
file_path.append(os.path.join(curDir, file))
img = Image.open(file_path[0])
new_dir = os.getcwd() + r'\triminged_image'#created new directory
os.makedirs(new_dir,exist_ok=True)
i = 0
img.save(new_dir + r'\sample{}.jpg'.format(i))#saved img to new directory with number i
二分探索の神みたいなコード
def meguru_bisect(ng, ok): ''' 初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す まずis_okを定義すべし ng ok は とり得る最小の値-1 とり得る最大の値+1 最大最小が逆の場合はよしなにひっくり返す ''' while (abs(ok - ng) > 1): mid = (ok + ng) // 2 if is_ok(mid): ok = mid else: ng = mid return ok
Class で DFS
DFSを毎回自力で実装するのがめんどくさいのでAtcoder のKiの問題をclassで実装したのでメモとして残します
以下 利用したコード
N,Q = map(int,input().split())
Graph = [[]for _ in range(N)]
operater = []
for _ in range(N-1):
a,b = map(int,input().split())
Graph[a-1].append(b-1)
Graph[b-1].append(a-1)
from collections import deque
q = deque()
q.append(0)
seen = [False for _ in range(N)]
parent = [[] for _ in range(N)]#i番目の値はi-1頂点の親のリスト
while q:
now = q.popleft()#int
seen[now] = True
next = Graph[now]#list
for ver in next:
if seen[ver] == False:
q.appendleft(ver)
parent[ver].append(now)#深さ優先探索で親を求めた
counter = [0 for _ in range(N)]
class DFS:
def __init__(self,N,Graph,parent,counter):
self.seen = [False for _ in range(N)]
self.delete = []
def children (self,st):#自分を含む子をすべて返す
self.ans = []
for i in parent[st]:
self.seen[i] = True
self.delete.append(i)
from collections import deque
q = deque()
q.append(st)
while q:
now = q.popleft() # int
self.seen[now] = True
next = Graph[now] # list
for ver in next:
if self.seen[ver] == False:
q.appendleft(ver)
for i,j in enumerate(self.seen):
if j == True and i not in self.delete:
self.ans.append(i)
self.seen = [False for _ in range(N)]
self.delete = []
return self.ans
def count(self,p,x):
self.c = self.children(p)
for i in self.c:
counter[i] += x
return counter
#このクラスでは予め親リストをつくって渡していることに注意。いつか親リストをつくるところもクラスにします。
