그린푸딩

//90도 회전tmp[j][N-1-i]=arr[i][j];//180도 회전tmp[N-1-i][N-1-j]=arr[i][j];//270도 회전tmp[N-1-j][i]=arr[i][j];

처음에 풀었을때 시간초과가 났었다. 푼 방식은 모든 간선(인접리스트로 구현) 을 하나씩 빼서 다시 인접리스트를 새로 만들고 다익스트라를 해보고 지연 시간을 측정하는것이었다.시간초과를 어떻게 줄일까 고민하다가 그래프를 인접행렬로 해야하면 새로 그래프 만들 필요 없어져서 줄어드려나? 했는데 이걸로도 부족했다.지문을 다시 보면 쓸데없는 간선을 삭제해봤자 도둑이 그 경로로 안가면 지연시간이 생길리가 없다.지문에 힌트가 있었다.사실 다른 블로그 힌트 봄..그래서 최단경로를 역추적해서 그 경로상의 간선 각각을 없앤 경우만 최단경로 시간을 구해서 지연시간을 계산하니까 시간초과가 해결되었다. 역시 골드 1인 이유가 있었다..#include#include#include#define INF 100000000using na..

다익스트라 시간복잡도 : ElogV (연결된 정점 탐색 x 가장가까운 지점 정렬) 다익스트라 주의점: 음의 가중치가 있을때 무한 사이클이 생길수 있음#include#include#include#define INF 100000000using namespace std; typedef pair ci; vector dijkstra(vector>&graph, vector&dist,int start) { priority_queue, greater>pq; dist[start] = 0; pq.push({ 0,start }); while (!pq.empty()) { int w = pq.top().first; int e = pq.top().second; pq.pop(); if (dist[e] (w + nw)..