Algoogle

Algorithm for Programming Contest

JOI 春合宿 2007 Route

Category: JOI Tag: dijkstra, geometry

Route

問題概要


n個の座標と, それらを繋ぐ重複しないm個のコスト付きの辺が与えられる.
3頂点を進むときそれらの成す角が鋭角にならないようにしか進めない.
1番目の頂点から2番目の頂点へ行く最小のコストを求めよ.

解法


1つ前の頂点と現在の頂点を状態とするDijkstraをやればよい.
鋭角かどうかは内積をとるなり, argを出して差をとるなりしてやれば良い.

コード


(Route.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0), eps = 1e-8;
const int inf = 1e9;
typedef complex<double> point;
typedef pair<int,int> pii;

struct node
{
        int u, v, c;
        bool operator<(const node &n) const { return c > n.c;}
};

int n, m, d[128][128];
vector<point> V;
vector<pii> G[128];

double arg(int u, int v, int w)
{
        point p = V[u], q = V[v], r = V[w];
        return arg(p-q)-arg(r-q);
}

bool can(double th)
{
        th = abs(th);
        if(th > pi) th -= 2*pi;
        return pi/2-eps < abs(th);
}

int solve()
{
        memset(d,-1,sizeof(d));
        priority_queue<node> q;
        for(auto &e: G[0]) q.push((node){0,e.first,e.second});

        int ans = inf;
        while(!q.empty()) {
                node a = q.top(); q.pop();
                if(d[a.v][a.u] >= 0) continue;
                d[a.v][a.u] = a.c;
                if(a.v == 1) ans = min(ans, a.c);
                for(auto &e: G[a.v])
                        if(can(arg(a.u,a.v,e.first)))
                                q.push((node){a.v, e.first, a.c+e.second});
        }

        return ans >= inf? -1: ans;
}

void input()
{
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
                int x, y;
                cin >> x >> y;
                V.push_back(point(x,y));
        }
        for (int i = 0; i < m; i++) {
                int x, y, c;
                cin >> x >> y >> c;
                x--; y--;
                G[x].push_back(pii(y,c));
                G[y].push_back(pii(x,c));
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments