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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <stdio.h> #include <vector> #include <queue> using namespace std; typedef struct node { int len, v1, v2; }; struct cmp { bool operator()(node a, node b) { return a.len > b.len; } }; int main() { int n1, n2; scanf("%d %d", &n1, &n2); vector<vector<int> > arr(n1+1, vector<int>(n2+1, 0)); vector<vector<int> > daiik(n1 + 1, vector<int>(n2 + 1, 300000000)); vector<vector<int> > visit(n1 + 1, vector<int>(n2 + 1, 0)); priority_queue<node, vector<node>, cmp > pq; for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { scanf("%d", &arr[i][j]); } } int a1, a2, b1, b2; scanf("%d %d", &a1, &a2); scanf("%d %d", &b1, &b2); node n; n.len = arr[a1][a2]; n.v1 = a1; n.v2 = a2; pq.push(n); visit[a1][a2] = 1; daiik[a1][a2] = arr[a1][a2]; while (pq.empty()==false) { node topN = pq.top(); pq.pop(); visit[topN.v1][topN.v2] = 1; if (topN.v1 + 1 <= n1 && visit[topN.v1 + 1][topN.v2]==0) { if (daiik[topN.v1 + 1][topN.v2] > daiik[topN.v1][topN.v2] + arr[topN.v1 + 1][topN.v2]) { daiik[topN.v1 + 1][topN.v2] = daiik[topN.v1][topN.v2] + arr[topN.v1 + 1][topN.v2]; node tmp; tmp.len = daiik[topN.v1 + 1][topN.v2]; tmp.v1 = topN.v1 + 1; tmp.v2 = topN.v2; pq.push(tmp); } } if (topN.v2 + 1 <= n2 && visit[topN.v1][topN.v2+1] == 0) { if (daiik[topN.v1][topN.v2 + 1] > daiik[topN.v1][topN.v2] + arr[topN.v1][topN.v2 + 1]) { daiik[topN.v1][topN.v2 + 1] = daiik[topN.v1][topN.v2] + arr[topN.v1][topN.v2 + 1]; node tmp; tmp.len = daiik[topN.v1][topN.v2 + 1]; tmp.v1 = topN.v1; tmp.v2 = topN.v2 + 1; pq.push(tmp); } } if (topN.v2 - 1 >= 1 && visit[topN.v1][topN.v2 - 1] == 0) { if (daiik[topN.v1][topN.v2 - 1] > daiik[topN.v1][topN.v2] + arr[topN.v1][topN.v2 - 1]) { daiik[topN.v1][topN.v2 - 1] = daiik[topN.v1][topN.v2] + arr[topN.v1][topN.v2 - 1]; node tmp; tmp.len = daiik[topN.v1][topN.v2 - 1]; tmp.v1 = topN.v1; tmp.v2 = topN.v2 - 1; pq.push(tmp); } } if (topN.v1 - 1 >= 1 && visit[topN.v1-1][topN.v2] == 0) { if (daiik[topN.v1 - 1][topN.v2] > daiik[topN.v1][topN.v2] + arr[topN.v1 - 1][topN.v2]) { daiik[topN.v1 - 1][topN.v2] = daiik[topN.v1][topN.v2] + arr[topN.v1 - 1][topN.v2]; node tmp; tmp.len = daiik[topN.v1 - 1][topN.v2]; tmp.v1 = topN.v1 - 1; tmp.v2 = topN.v2; pq.push(tmp); } } } printf("%d", daiik[b1][b2]); } | cs |
'알고리즘 > 다익스트라' 카테고리의 다른 글
silver cow party (더블릿) (0) | 2019.05.18 |
---|---|
다익스트라 최단거리 (더블릿) (0) | 2019.05.18 |