bright

www.acmicpc.net/problem/1753

import sys
import heapq 
input = sys.stdin.readline

V,e = map(int,input().split()) # 정점, 간선 
k = int(input()) # 시작 

graph = [ [] for _ in range(V+1)]

for i in range(e):
  u,v,w = map(int,input().split())
  graph[u].append( (v,w) ) # 이어진 곳, 거리 

# 경로 존재하지 않으면 INF 

def dij(start):
  q = []
  dist = [1e9]*(V+1)
  heapq.heappush(q, (0,k) )
  dist[start]=0
  

  while q:
    d, now = heapq.heappop(q)

    if dist[now]< d : continue # 전에 방문한 적 있으면 처리하지 않음 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]] :
        dist[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))
  return dist 

result = dij(k)

for i in range(1,V+1):
  if result[i] == 1e9 : 
    print("INF")
  else:
    print(result[i])

정점 대문자 V 

중간에 입력 받는거 소문자 v.... 

www.acmicpc.net/problem/10942

# 시간 초과

from collections import deque

n = int(input())
data = list(map(int,input().split()))
m = int(input())

result = [1]*m 

for i in range(m):
  s,e = map(int,input().split())
  if e-s <2 : continue 
  d = deque(data[s-1:e]) 
  while len(d) > 1 :
    if d.pop() != d.popleft() : 
      result[i] = 0 

for i in range(m): print(result[i])

# 정답 ( dp ) 

www.acmicpc.net/problem/10211

t = int(input())

def max_sub():
  n = int(input())
  data = list(map(int,input().split())) 

  for i in range(1,len(data)):
    data[i] += data[i-1] if data[i-1]>0 else 0
  
  return max(data)

p = []

for i in range(t):
  p.append(max_sub())

for i in range(t):
  print(p[i])

www.acmicpc.net/problem/1890

import sys
n = int(input())

graph = [list(map(int, input().split())) for i in range(n)]

d = [ [0]*n for _ in range(n) ] 
d[0][0] = 1

for i in range(n):
  for j in range(n):
    if i == j == n-1 : break 
    a = graph[i][j]

    if i+ a < n :
      d[i+a][j] += d[i][j]
    if j+a < n : 
      d[i][j+a] += d[i][j]

print(d[n-1][n-1])

d[n-1][n-1] = 0 은 항상 만족하는 조건이다. 

만약  이중 for 문에서 n-1, n-1 인 경우를 빼지 않으면 a = 0이고 i+a<n 과 j+a<n 이 모두 True 가 되어 

더하지 않아도 되는 계산을 하게 된다. 

따라서 맨 마지막 경우를 빼는 조건을 반드시 넣어 주도록 한다. 

www.acmicpc.net/problem/1743

from collections import deque

n, m , k = map(int,input().split()) # 세로 가로 음식물 수 
graph = [ [0]*m for i in range(n)]
for i in range(k):
  a,b = map(int,input().split())
  graph[a-1][b-1] = 1 


dx = [-1,1,0,0]
dy = [0,0,1,-1]

def bfs(x,y):
  q = deque()
  q.append((x,y))
  graph[x][y] = 0 
  cnt = 1 

  while q : 
    a, b= q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]

      if nx<0 or nx>=n or ny<0 or ny>=m : 
        continue 
      if graph[nx][ny] == 1:
        cnt += 1 
        q.append((nx,ny))
        graph[nx][ny] = 0 
  return cnt 

tmp = 0 

for i in range(n):
  for j in range(m):
    if graph[i][j] != 0 :
      tmp = max(tmp, bfs(i,j))

print(tmp)