[Codeground 46번] 할인권

문제 출처 :

https://www.codeground.org/practice/practiceProblemList

알고리즘 분석 :

문제 해결에 필요한 사항

1. 플로이드 워셜 알고리즘 :: http://www.crocus.co.kr/search/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C

문제를 보면 최단 거리 문제임을 알 수 있다.

그리고 쿼리가 존재하는 문제이고, N 제한은 100이다.

이때 알아 낼 수 있는 부분은 최단거리, n제한을 고려하면 플로이드 워셜 알고리즘 이라는 것을 알아낼 수 있다.

플로이드 알고리즘을 이용하여 모든 경로마다 다른 경로의 최단 거리를 알게 되면 쿼리가 O(1)에 끝이나게 된다.

따라서 이 문제의 시간 복잡도는 O(n^3)에 해결 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include <iostream> #include <cstdio> #include <vector> #include <memory.h>   #define INF 987654321   using namespace std; typedef pair<int, int> pii;   int adj[105][105]; int cost[105][105];   int main() {     int tc;     scanf("%d", &tc);       for(int tCase = 1; tCase <= tc; tCase++)     {         int V, E, k;         memset(adj, 0, sizeof(adj));         memset(cost, 0, sizeof(cost));           vector<pii> trip;         scanf("%d %d %d", &V, &E, &k);              for (int i = 0; i <= V; i++)             for (int j = 0; j <= V; j++)                 i == j ? adj[i][j] = 0 : adj[i][j] = INF;           for (int i = 0; i < E; i++)         {             int from, to, val;             scanf("%d %d %d", &from, &to, &val);               adj[from][to] = val;             adj[to][from] = val;         }           int n;         scanf("%d", &n);           for (int i = 0; i < n; i++)         {             int from, to;             scanf("%d %d", &from, &to);               trip.push_back(pii( from, to ));         }           for (int k = 1; k <= V; k++)             for (int x = 1; x <= V; x++)                 for (int y = 1; y <= V; y++)                     if (adj[x][y] > adj[x][k] + adj[k][y])                         adj[x][y] = adj[x][k] + adj[k][y];           int cnt = 0;         for (int i = 0; i < trip.size(); i++)         {             int from = trip[i].first;             int to = trip[i].second;               if (adj[from][to] > k)                 cnt++;         }           printf("Case #%d\n%d\n", tCase, cnt);     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus