lastknight00

문제 링크 : [백준]도로포장(1162) 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 문제 설명 N개의 노드와 M개의 양방향 간선 정보가 주어집니다. 이 때, 1번 노드에서 N번 노드로 이동하는데, K개의 간선의 비용을 0으로 변경 할 수 있습니다. 1번 노드에서 N번 노드까지의 최단거리를 구하세요. 입력 N(노드의 갯수, 1

문제 링크 : [백준]특정한 최단 경로(1504) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 설명 1번 노드에서 N번노드까지 가는데 특정한 두 노드를 거쳐서 가는 최단 거리를 구하세요. 입력 N(노드의 갯수, 1 V2->V1->도착점 두 가지 중 하나의 경우 일 것입니다. 시작점을 기준으로 다익스트라를 돌리게 되면, 시작점에서 V1, V2, 도착점 까지의 최단 거리를 구할 수 있습니다. 마찬가지로, V1, V2를 기준으로 돌리면 각 노드를 시작점으로 하여..

문제 링크 : [백준]The Other Way(14554) 14554번: The Other Way 첫째 줄에는 $N$, $M$, $S$, $E$가 하나의 공백으로 구분되어 들어온다. ($2 \le N \le 100000$, $N-1 \le M \le 300000$, $1 \le S, E \le N$, $S \neq E$) 그 후 $M$개의 줄에는 $A$, $B$, $C$가 하나의 공백으로 구분 되어 들어 www.acmicpc.net 문제 설명 N개의 노드와 M개의 양방향 간선이 주어질 때, 시작점에서 도착점까지 최단거리로 가는 경로의 갯수를 구하세요. 입력 N(노드의 갯수, 1 m>>s>>e; for(x=1;x>x>>y>>z; v[x].push_back({y,z}); v[y].push_back({x,z}..

문제 링크 : [백준]거의 최단 경로(5719) 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 www.acmicpc.net 문제 설명 N개의 도시가 있고, M개의 도로 정보가 주어집니다. 이때, 시작점부터 도착점까지 가는 최단거리를 구성하는 모든 도로를 제외한 도로들을 가지고 최단거리를 구하세요. 입력 N(도시의 수, 1

문제 링크 : [백준]미로에 갇힌 건우(18224) 문제 설명 N * N 지도가 주어집니다. 0은 빈 칸, 1은 벽입니다. (1,1)에서 출발하여, (N,N)까지 이동하는데, 벽은 밤에만 넘어갈 수 있고, 진행 방향으로 이어진 벽을 한번에 넘어가야 합니다. 벽을 타고 나면서 지도를 벗어나는 경우는 이동할 수 없습니다. 밤/낮에 몇칸을 이동 할 수 있는지가 주어졌을 때, 목적지로 가장 빠르게 이동하였을 때, 몇번째 날의 낮/밤 여부를 구하세요. 입력 N(지도의 크기, 1 m;m--; for(i=0;id[i][j]; q.push(N(1,m,0,0,1)); v[0][0][1][m]=1; while(!q.empty()){ N c=q.front();q.pop(); if(c.x==n-1&&c.y==n-1){ cout

문제 링크 : [백준]무엇을 아느냐가 아니라 누구를 아느냐가 문제다(9694) 문제 설명 0번 노드에서 N-1번 노드까지의 최단거리를 가는 경로를 구하세요. 입력 T(테스트 케이스, 1 < T < 100) N(엣지의 갯수, N

문제 링크 : [백준]민준이와 마산 그리고 건우(18223) 문제 설명 1번 노드에서 V번까지 가는 최단거리가 1번에서 P번 노드를 거쳐 V번 노드까지 가는 최단거리보다 작거나 같은지 판별하세요. 입력 V(노드의 갯수, 1 1로 가는 최단거리 + P -> V로 가는 최단거리를 더하면 됩니다. 시간복잡도 O(M * logM) 코드 #include #include #include #include #include #define N 5001 using namespace std; typedef pairP; int n,m,p,a,b,c,d[N],e[N],w[N]; vectorv[N]; priority_queueq; void r(int s,int d[]){ memset(w,0,sizeof(w)); q.push({0,..

문제 링크 : [백준]간선 이어가기 2(14284) 문제 설명 연결이 없는 노드 N개가 주어집니다. 그 이후에 M개의 무방향 가중치 엣지가 주어집니다. 출발지 S와 도착지 T가 주어지면, 이전에 주어진 간선들의 순서를 원하는대로 바꾸고 순서대로 하나씩 간선을 이어나가다가 S와 T가 이어지는 순간 작업을 멈춥니다. 이때 이은 간선들의 가중치의 합의 최소값을 구하세요. 입력 N(노드의 갯수, 1 a>>b>>c; v[a].push_back({c,b}); v[b].push_back({c,a}); } cin>>a>>b; q.push({0,a}); while(!q.empty()){ P x=q.top();q.pop(); if(d[x.second])continue; d[x.second]=1; if(x.second==b..