글 읽기 - 파이썬 반례좀 찾아주세요 ᅮᅮ

(追記) (追記ここまで)

파이썬 반례좀 찾아주세요 ᅮᅮ

17270번 - 연예인은 힘들어

ris33 4년 전 0

heapq을 안써도 여러방법이 있긴하지만

모든 경우가 다 맞는것 같은데 100프로에서 틀리네요

import sys
import heapq
from collections import deque
input=sys.stdin.readline
v,m=map(int,input().split())
data=[[] for _ in range(v+1)]
for _ in range(m):
 a,b,c=map(int,input().split())
 data[a].append((b,c))
 data[b].append((a,c))
j,s=map(int,input().split())
INF=int(1e9)
def dijkstra(start):
 distance=[INF]*(v+1)
 distance[start]=0
 q=deque()
 q.append((0,start))
 while q:
 km,index=q.popleft()
 if distance[index]<km:
 continue
 for i in data[index]:
 cost=km+i[1]
 if cost<distance[i[0]]:
 distance[i[0]]=cost
 q.append((cost,i[0]))
 return distance
jihun=dijkstra(j)
sungha=dijkstra(s)
result=[]
for i in range(1,v+1):
 if i!=j and i!=s:
 result.append((jihun[i]+sungha[i],i))
heapq.heapify(result)
sibal=result[0][0]
if len(result)==0:
 print(-1)
else:
 mak=[]
 while result:
 cost,index=heapq.heappop(result)
 if cost>sibal:
 continue
 if sungha[index]>jihun[index]:
 mak.append(index)
 if len(mak)==0:
 print(-1)
 else:
 heapq.heapify(mak)
 print(mak[0])

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

파이썬 반례좀 찾아주세요 ᅮᅮ

ris33 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말