//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
#include<string>
#include<sstream>
using namespace std;

const int N = 50010, M = 200010, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int source[7], dist[7][N];
int us[N],st[N];
int n, m;
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 diji(int start,int id) {
    memset(us, 0, sizeof us);
    dist[id][start] = 0;
    priority_queue<PII, vector<PII>, greater<PII>>heap;
    heap.push({ 0,start });
    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.second,  dis = t.first;
        if (us[ver] == 1)continue;
        us[ver] = 1;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (us[j] == 0 && dist[id][j] > dis + w[i]) {
                dist[id][j] = dis + w[i];
                heap.push({ dist[id][j],j });
            }
        }
    }
}

int dfs(int u, int start, int distance) {
    if (u == 6)return distance;

    int res = INF;
    for (int i = 1; i <= 5; i++) {
        if (st[i] == 0) {
            int next = source[i];
            st[i] = 1;
            res = min(res, dfs(u + 1, i, distance + dist[start][next]));
            st[i] = 0;
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    source[0] = 1;
    for (int i = 1; i <= 5; i++)cin >> source[i];
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < 6; i++)diji(source[i],i);

    cout << dfs(1, 0, 0);

    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
#include<string>
#include<sstream>
using namespace std;

const int N = 110;
int m, n;
int r[N];
int w[N][N];
int dist[N], st[N];

int diji(int lt, int rt) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0] = 0;
    for (int i = 0; i <= n; i++) {
        int t = -1;
        for (int j = 0; j <= n; j++) {
            if (st[j] == 0 && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        st[t] = 1;
        for (int j = 1; j <= n; j++) {
            if (r[j] >= lt && r[j] <= rt) {
                dist[j] = min(dist[j], dist[t] + w[t][j]);
            }
        }

    }
    return dist[1];
}


int main() {
    cin >> m >> n;
    memset(w, 0x3f, sizeof w);
    for (int i = 1; i <= n; i++) {
        int price, num;
        cin >> price >> r[i] >> num;
        w[0][i] = min(price,w[0][i]);
        for (int j = 1; j <= num; j++) {
            int no, cost;
            cin >> no >> cost;
            w[no][i] = min(cost,w[no][i]);
        }
    }

    int res = 0x3f3f3f3f;

    for (int i = r[1] - m; i <= r[1]; i++)res = min(res, diji(i, i + m));

    cout << res;

    return 0;
}

#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
#include<string>
#include<sstream>
using namespace std;

const int N = 510;
int w[N][N];
int dist[N];
int m, n;
int stop[N];

void bfs() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int>q;
    q.push(1);
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (dist[i] == 0x3f3f3f3f && w[t][i]==1) {
                q.push(i);
                dist[i] = dist[t] + 1;
            }
        }
    }
}

int main() {
    cin >> m >> n;
    string no_use;
    getline(cin, no_use);
    while (m--) {
        string line;
        getline(cin, line);
        stringstream ssin(line);
        int idx = 0, num;
        while (ssin >> num)stop[idx++] = num;
        for (int i = 0; i < idx; i++) {
            for (int j = i+1; j < idx; j++) {
                w[stop[i]][stop[j]] = 1;
            }
        }
    }

    bfs();
    if (dist[n] == 0x3f3f3f3f)cout << "NO";
    else cout << dist[n] - 1;
    return 0;
}

#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 2010;
double w[N][N];
double dist[N];
int n, m;
int st[N];
int A, B;

double dj() {
    dist[A] = 1;
    for (int i = 1; i <= n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (st[j] == 0 && (t == -1 || dist[j] > dist[t])) {
                t = j;
            }
        }
        st[t] = 1;
        for (int i = 1; i <= n; i++) {
            dist[i] = max(dist[i], dist[t] * w[t][i]);
        }
    }
    return dist[B];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        w[a][b] = w[b][a] = max(w[a][b], (100.0-c)/100);
    }


    cin >> A >> B;

    printf("%.8f", 100 / dj());

    return 0;
}

#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 810, M = 3000;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], st[N];
int id[M];
int n, p, c;
const int INF = 0x3f3f3f3f;

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

int spfa(int start) {
    memset(dist, 0x3f, sizeof dist);
    st[start] = 1;
    queue<int>q;
    dist[start] = 0;
    q.push(start);
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = 0;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (st[j] == 0) {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        int t = id[i];
        if (dist[t] == INF) {
            res = INF;
            return INF;
        }
        else {
            res += dist[t];
        }
    }
    return res;
}

int main() {
    cin >> n >> p >> c;
    for (int i = 1; i <= n; i++)cin >> id[i];

    memset(h, -1, sizeof h);

    for (int i = 0; i < c; i++) {
        int aa, bb, cc;
        cin >> aa >> bb >> cc;
        add(aa, bb, cc);
        add(bb, aa, cc);
    }

    int res = INF;
    for (int i = 1; i <= p; i++) {
        res = min(res, spfa(i));
    }
    cout << res;
    return 0;
}

#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 105;
int dist[N][N];
int n, m;

int main() {
    cin >> n >> m;
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i ++ ) dist[i][i] = 0;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = dist[b][a] = min(dist[a][b], c);
    }



    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[1][i] == 0x3f3f3f3f) {
            res = -1;
            break;
        }
        else res = max(res, dist[1][i]);
    }
    cout << res;
    return 0;
}

#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 2510, M = 12410;
int T, C, Ts, Te;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], 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(dist, 0x3f, sizeof dist);
    queue<int>q;
    dist[Ts] = 0;
    st[Ts] = 1;
    q.push(Ts);
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (st[j] == 0) {
                    q.push(j);
                }
            }
        }
    }
}

int main() {
    cin >> T >> C >> Ts >> Te;
    memset(h, -1, sizeof h);
    for (int i = 0; i < C; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    spfa();
    cout << dist[Te];
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 104*2;
int w[N];
int f[N][N];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[n + i] = w[i];
    }



    for (int len = 3; len <= n + 1; len++) {
        for (int l = 1; l + len - 1 <= 2 * n; l++) {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k++) {
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
            }
        }
    }
    int maxv = -0x3f3f3f3f;

    for (int i = 1; i <= n; i++) {
        int j = i + n;
        maxv = max(maxv, f[i][j]);
    }
    cout << maxv;
    return 0;
}

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N = 405;
int f1[N][N], f2[N][N];
int w[N];
int s[N];
int n;
const int INF = 0x3f3f3f3f;

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
w[i + n] = w[i];
}

for (int i = 1; i <= 2 * n; i++)s[i] = s[i - 1] + w[i];

memset(f1, 0x3f, sizeof f1);
memset(f2, -0x3f, sizeof f2);

for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= 2 * n; l++) {
        int r = l + len - 1;
        if (len == 1)f1[l][r] = f2[l][r] = 0;
        else {
            for (int k = l; k < r; k++) {
                f1[l][r] = min(f1[l][r], f1[l][k] + f1[k + 1][r] + s[r] - s[l - 1]);
                f2[l][r] = max(f2[l][r], f2[l][k] + f2[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }
}
int maxv = -INF, minv = INF;
for (int i = 1; i <= n; i++) {
    maxv = max(maxv, f2[i][i + n - 1]);
    minv = min(minv, f1[i][i + n - 1]);
}
cout << minv << endl << maxv;

return 0;

}

```

#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 18;
int s[N][N];
int f[1 << N];
int t, n, m, no_use;
typedef pair<double, double> PDD;
PDD d[N];
const double dlt = 1e-6;
int cmp(double a, double b) {
    if (abs(a - b) < dlt)return 0;
    if (a - b < 0)return -1;
    return 1;
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> no_use;
        for (int i = 0; i < n; i++)cin >> d[i].first >> d[i].second;
        memset(s, 0, sizeof s);
        memset(f, 0x3f, sizeof f);
        for (int i = 0; i < n; i++) {
            s[i][i] = 1 << i;
            for (int j = 0; j < n; j++) {
                double x1 = d[i].first, y1 = d[i].second;
                double x2 = d[j].first, y2 = d[j].second;
                if (cmp(x1, x2) == 0)continue;
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                if (cmp(a,0) >= 0)continue;

                for (int k = 0; k < n; k++) {
                    if (cmp(a * d[k].first * d[k].first + b * d[k].first, d[k].second) == 0) {
                        s[i][j] += 1 << k;
                    }
                }
            }
        }
        f[0] = 0;
        for (int i = 0; i < (1 << n) - 1; i++) {
            int x = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) == 0)x = j;
            }

            for (int j = 0; j < n; j++) {
                f[i | s[x][j]] = min(f[i | s[x][j]], f[i] + 1);
            }
        }
        cout << f[(1 << n) - 1] << endl;

    }
    return 0;
}