너와 나의 스토리

문제: www.acmicpc.net/problem/1753 소스 코드: #include #include #include #include #include #include #define inf 1000000000 using namespace std; typedef pair PI; int vertex, edge, start; int dist[20002]; bool visit[20002]; vector adj; void dijkstra() { fill(dist, dist + vertex + 1, inf); priority_queue pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int cur; do { cur = pq.top().second; ..

문제: https://www.acmicpc.net/problem/5719 문제 풀이: 다익스트라 한 번 돌리고 뒤에서부터 최단 경로인 것들 다 지운 다음에 다익스트라 다시 돌림 소스코드: #include #include #include #include #include #define inf 5000001 using namespace std; typedef pair P; int n, m,dist[501],adj[501][501]; bool visit[501]; void di(int start,int end) { fill(dist, dist + n+1, inf); priority_queue pq; memset(visit, false, sizeof(visit)); dist[start] = 0; pq.push({..

문제: https://www.acmicpc.net/problem/15971 방법 1: 1. 다익스트라 돌려서 a에서 b까지 최단 경로를 찾는다. (변수명: a->src, b->dest) 2. 두 로봇은 한 칸 떨어졌을때 통신 가능하다 최단 경로 중 edge 하나를 뺀 것과 동일 끝 점부터 최단 경로를 추적하면서 제일 weight이 큰 edge를 찾아서 최단 경로 cost - maxW을 결과로 출력한다. 소스코드: #include #include #include #include #include #define inf 1000000000 using namespace std; typedef long long ll; typedef pair P; int n,m,src,dest; int dist[100002],max..

문제: https://www.acmicpc.net/problem/13911 문제 풀이: 맥도날드가 있는 곳, 스타벅스가 있는 곳에서 각각 시작해서 다익스트라 돌림 각 정점을 입력 받을 때 pq에 (0,시작정점)으로 넣어넣고 시작하면 한번에 돌릴 수 있음 소스 코드: typedef pair P; int n, m, macs, stars, x, y, dist[2][10001],res=inf; bool visit[2][10001]; vector adj; typedef priority_queue Prior; Prior tmp,tmp2; void di(int cnt,Prior pq) { while (!pq.empty()) { int cur; do { cur = pq.top().second; pq.pop(); } w..

문제: https://www.acmicpc.net/problem/14618 문제풀이: 1. 진서집에서 시작해서 다익스트라 돌리기 (양방향) 2. 진서가 가장 빨리 갈 수 있는 집 찾기 B집부터 비교해서 갱신해주고 그 후, A집 비교해줘서 B집이랑 같은 거리이면 A 출력하기 소스코드: #define inf 987654321 using namespace std; typedef pair P; int n, m, jinsu, k,dist[5001]; bool visit[5001]; vector a, b; vector adj; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m;..

문제: https://www.acmicpc.net/problem/10282 문제 풀이: "단방향"으로 감염됨! a,b,s이면 b->a 감염시키고 a->b 감염 못 시킴 처음 감염된 컴퓨터 기준으로 다익스트라 돌림 그리고 1~N까지 포문 돌리면서 dist[i]!=inf (감염되지 않지 않았다면) cnt++; dist 중에 가장 큰 수가 감염되기까지 걸리는 시간이다. 소스 코드: typedef pair P; vector v; int tc, dist[10001], n, m, k; bool visit[10001]; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> tc; while (t..

문제: https://www.acmicpc.net/problem/6118 문제 풀이:- 다익스트라 돌려서 1에서 각 점까지의 최단 거리 구함- 구해놓은 dist를 처음부터 끝까지 보면서 제일 큰 수와 그 수의 개수를 찾음 소스 코드: #include #include #include #include #include #define inf 987654321using namespace std; typedef pair P;int n, m,dist[20001],t,cnt;bool visit[20001]; int main() {ios::sync_with_stdio(false);cin.tie(NULL), cout.tie(NULL); cin >> n >> m; vector adj;adj.resize(n + 1);for ..

문제: https://www.acmicpc.net/problem/6593 문제 풀이:- 다익스트라 이용 - 동,서,남,북,상,하 이동int dx[6] = { 0,0,1,0,-1,0 };int dy[6] = { 0,0,0,1,0,-1 };int dh[6] = { 1,-1,0,0,0,0 }; - tuple 이용해서 priority_queue에 저장 * tuple 설명ㄴ 여러가지 변수를 묶을 수 있다 (pair랑 비슷)ㄴ tuple t = make_tuple(1,2,3); // 값 삽입ㄴ int a=get(t); // t의 0번째 값 받아오기 소스 코드: #include #include #include #include #include #include #define inf 1000000000using names..