#include <bits/stdc++.h>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int h[N], e[N], ne[N], w[N], idx;
int d[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[t] + w[i]) {
                d[j] = d[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    memset(h, -1, sizeof h);
    while (m -- ) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }

    spfa();

    if (d[n] == INF) cout << "impossible" << endl;
    else cout << d[n] << endl;

    return 0;
}

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        for (int i = 0; i < s.size(); i ++ ) {
            int j = i;
            while (j < s.size() && s[j] != ' ') j ++ ;
            reverse(s.begin() + i, s.begin() + j);
            i = j;
        }
        return s;
    }
};

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int s[N], t[N];

int main() {
    int n;
    while (cin >> n, n) {
        for (int i = 0; i < n; i ++ ) cin >> s[i];
        for (int i = 0; i < n; i ++ ) cin >> t[i];
        sort(s, s + n, greater<int>());
        sort(t, t + n, greater<int>());

        int res = 0;
        int i = 0, j = n - 1, k = 0, l = n - 1;
        while (i <= j) {
            if (s[i] > t[k]) {
                res ++ ;
                i ++ , k ++ ;
            } else if (s[i] < t[k]) {
                res -- ;
                j -- , k ++ ;
            } else if (s[i] == t[k]) {
                if (s[j] < t[l]) {
                    res -- ;
                    j --, k ++ ;
                } else if (s[j] > t[l]) {
                    res ++ ;
                    j -- , l -- ;
                } else if (s[j] == t[l]) {
                    if (s[j] < t[k]) res -- ;
                    j -- , k ++ ;
                }
            }
        }
        cout << res * 200 << endl;
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 300010;
int e[M], h[N], ne[M], w[M], idx;
int d[N];
bool st[N];
int n, m, k, q, x;

typedef pair<int, int> PII;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[0] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 0});

    while (q.size()) {
        auto t = q.top();
        q.pop();

        int v = t.second;
        if (st[v]) continue;
        st[v] = true;

        for (int i = h[v]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[v] + w[i]) {
                d[j] = d[v] + w[i];
                q.push({d[j], j});
            }
        }
    }
}

int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);
    while (m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    cin >> k;
    while (k -- ) {
        cin >> x;
        add(0, x, 0);
    }

    dijkstra();

    cin >> q;
    while (q -- ) {
        cin >> x;
        cout << d[x] << endl;
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n1, n2, m;
    cin >> n1 >> n2 >> m;

    int x;
    vector<int> f(m + 1);
    f[0] = 1;
    for (int i = 1; i <= n1; i ++ ) {
        cin >> x;
        for (int j = x; j <= m; j ++ ) f[j] = (f[j] + f[j - x]) % MOD;
    }

    for (int i = 1; i <= n2; i ++ ) {
        cin >> x;
        for (int j = m; j >= x; j -- ) f[j] = (f[j] + f[j - x]) % MOD;
    }

    cout << f[m] << endl;

    return 0;
}

做法一：前后两次DP

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n;
    cin >> n;

    vector<int> s(n);
    for (int i = 0; i < n; i ++ ) cin >> s[i];

    vector<int> f(n);
    for (int i = n - 2, maxV = s[n - 1]; i >= 0; i -- ) {
        f[i] = max(f[i + 1], maxV - s[i]);
        maxV = max(maxV, s[i]);
    }

    vector<int> g(n);
    for (int i = 1, minV = s[0]; i < n; i ++ ) {
        g[i] = max(s[i] - minV, g[i - 1]);
        minV = min(minV, s[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, g[i] + f[i]);
    cout << res << endl;

    return 0;
}

做法二：状态机DP

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n;
    cin >> n;

    vector<vector<int>> f(n + 1, vector<int>(5, -1e9));

    f[0][0] = 0;
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;

        f[i][0] = f[i - 1][0];
        f[i][1] = max(f[i - 1][1], f[i - 1][0] - x);
        f[i][2] = max(f[i - 1][2], f[i - 1][1] + x);
        f[i][3] = max(f[i - 1][3], f[i - 1][2] - x);
        f[i][4] = max(f[i - 1][4], f[i - 1][3] + x);
    }

    cout << max(f[n][0], max(f[n][2], f[n][4])) << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, INF = 1e9;
typedef pair<int, int> PII;

int a[N][N], d[N][N];

int main() {
    int n, m;
    cin >> n >> m;

    queue<PII> q;
    memset(d, 0x3f, sizeof d);

    for (int i = 0; i < n; i ++ ) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j ++ ) {
            if (s[j] == '1') {
                q.push({i, j});
                d[i][j] = 0;
            }
        }
    }

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    while (q.size()) {
        auto t = q.front();
        q.pop();

        int x = t.first, y = t.second;
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (d[a][b] > d[x][y] + 1) {
                d[a][b] = d[x][y] + 1;
                q.push({a, b});
            }
        }
    }

    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) cout << d[i][j] << ' ';
        cout << endl;
    }

    return 0;
}

#include <iostream>

using namespace std;

const int N = 100010;

int a[N], b[N];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) b[i] = a[i] - a[i - 1];

    while (m -- ) {
        int l, r, c;
        cin >> l >> r >> c;

        b[l] += c, b[r + 1] -= c;
    }

    int sum = 0;
    for (int i = 1; i <= n ; i ++ ) {
        sum += b[i];
        cout << sum << ' ';
    }

    return 0;
}

#include <iostream>

using namespace std;

const int N = 1010;

int a[N];

int main() {
    int T;
    cin >> T;
    while (T -- ) {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < m; i ++ ) cin >> a[i];

        int res = 0, k = (n - 1) % m;
        for (int i = 1; i <= n - 1; i ++ ) {
            res = (res + a[(k - 1 + m) % m]) % (i + 1);
            k = (k - 1 + m) % m;
        }
        cout << res << endl;
    }

    return 0;
}

#include <iostream>

using namespace std;

const int N = 5010, M = 8192, MOD = 1e9 + 7;

int f[2][M], a[N];

bool is_prime(int x) {
    for (int i = 2; i * i <= x; i ++ ) {
        if (x % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j < M; j ++ ) 
            f[i & 1][j] = (f[i - 1 & 1][j] + f[i - 1 & 1][j ^ a[i]]) % MOD;

    int res = 0;
    for (int i = 2; i < M; i ++ )
        if (is_prime(i)) res = (res + f[n & 1][i]) % MOD;

    cout << res << endl;

    return 0;
}