Nguy hiểm rõ ràng trước mắt

Điểm: 0,12 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

USACO US-Open 2008 - Bảng Bạc

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nông dân John đang ở trên một con thuyền nhỏ và đang tìm kiếm kho báu ở $1$ trong số $N$ $(1 \leq N \leq 100)$ hòn đảo $($ đánh số từ $1. . . N)$ ở vùng biển Ca-ri-bò.

Bản đồ kho báu cho John biết John cần phải thực hiện $1$ hành trình đi qua đảo $A_{1}$ , $A_{2}$ , ..., $A_{M}$ $(2 \leq M \leq 10,000)$ , bắt đầu từ đảo $1$ và kết thúc ở đảo $N$ trước khi kho báu biến mất. Anh ta có thể đến thăm các đảo khác và thăm bao nhiêu lần tùy thích, miễn là hành trình của ông ta phải chứa dãy $A_{1}$ , ..., $A_{M}$ là $1$ dãy con (không nhất thiết phải liên tiếp nhau).

John muốn tránh đụng độ cướp biển và biết được mức-độ-bị-cướp $(0 \leq$ mức-độ-bị-cướp $\leq 100,000)$ khi đi lại giữa $2$ hòn đảo với nhau. Độ nguy hiểm của hành trình của John sẽ là tổng các mức-độ-bị-cướp trên các tuyến đường mà John đi qua.

Hãy giúp John tìm được $1$ hành trình ít nguy hiểm nhất để có thể lấy được kho báu.

Input

Dòng $1$ : $2$ số nguyên cách nhau bởi dấu cách: $N$ và $M$
Dòng $2. . . M + 1$ : Dòng $i + 1$ mô tả chứa $1$ số nguyên là đảo thứ $i$ mà John cần phải tới: $A_{i}$
Dòng $M + 2. . . N + M + 1$ : Dòng $i + M + 1$ chứa $N$ số nguyên cách nhau bởi dấu cách tương ứng là mức-độ-bị-cướp trên tuyến đường đi giữa đảo $i$ và đảo $1$ , $2$ , ..., $N$ ; đảm bảo số nguyên thứ $i$ luôn là số $0$ .

Output

Dòng $1$ : Độ nguy hiểm nhỏ nhất của hành trình của John.

Sample Input

Copy

Sample Output

Copy

Note

Có $3$ hòn đảo và bản đồ kho báu yêu cầu John phải thực hiện $1$ hành trình tới các đảo như sau: từ đảo $1$ tới đảo $2$ , quay lại đảo $1$ và cuối cùng là tới đảo $3$ . Mức-độ-bị-cướp trên các tuyến đường đã được cho: $(1$ , $2)$ ; $(2$ , $3)$ ; $(3$ , $1)$ có độ lớn tương ứng là $5$ , $2$ và $1$ .
Hành trình có độ nguy hiểm nhỏ nhất là $7$ . John sẽ đi như sau: $1$ , $3$ , $2$ , $3$ , $1$ , and $3$ . Yêu cầu của bản đồ là phải chứa dãy $(1$ , $2$ , $1$ , và $3)$ và hành trình này thỏa mãn yêu cầu. Chúng ta sẽ tránh đi trên đường nối giữa $2$ đảo $1$ và $2$ vì nó có mức-độ-bị-cướp lớn.

Bình luận

Hãy đọc nội quy trước khi bình luận.

-8
nguyenthihai14121980 đã bình luận 3:39:50 ch, 25/07/2024
tron vn goi y

include <bits/stdc++.h>

using namespace std;

typedef long long ll; typedef pair<int,int> ii; typedef unsigned long long ull;

define X first

define Y second

define pb push_back

define mp make_pair

define ep emplace_back

define EL printf("\n")

define sz(A) (int) A.size()

define FOR(i,l,r) for (int i=l;i<=r;i++)

define FOD(i,r,l) for (int i=r;i>=l;i--)

define fillchar(a,x) memset(a, x, sizeof (a))

define faster iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 101, inf = 1e9; int n, m, d[N][N], f[10002]; vector<ii> a[N];

struct data { int u, c; bool operator < (const data &o) const { return c > o.c; } };

void dijkstra(int s) { priority_queue<data> st; FOR(i,1,n) d[s][i] = inf; d[s][s] = 0; st.push({s, d[s][s]}); while (! st.empty()) { int u = st.top().u, c = st.top().c; st.pop(); if (c > d[s][u]) continue; for (auto k : a[u]) { int v = k.X, w = k.Y; if (d[s][v] > d[s][u] + w) { d[s][v] = d[s][u] + w; st.push({v, d[s][v]}); } } } }

int main() { // freopen("INP.TXT", "r", stdin); // freopen("OUT.TXT", "w", stdout);

Copy
scanf("%d%d", &n,&m); FOR(i,1,m) scanf("%d", &f[i]); FOR(u,1,n) { FOR(v,1,n) { int c; scanf("%d", &c); if (u == v) continue; a[u].pb({v,c}); } } FOR(s,1,n) dijkstra(s); f[0] = 1; f[++m] = n; ll ans = 0ll; FOR(i,0,m-1) ans += d [ f[i] ] [ f[i+1] ]; printf("%lld\n", ans); return 0;

}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6
nguyenthihai14121980 đã bình luận 3:34:26 ch, 25/07/2024
goi yyyyy

define Y second

define pb push_back

define mp make_pair

define ep emplace_back

define EL printf("\n")

define sz(A) (int) A.size()

define FOR(i,l,r) for (int i=l;i<=r;i++)

define FOD(i,r,l) for (int i=r;i>=l;i--)

define fillchar(a,x) memset(a, x, sizeof (a))

define faster iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 101, inf = 1e9; int n, m, d[N][N], f[10002]; vector<ii> a[N];

struct data { int u, c; bool operator < (const data &o) const { return c > o.c; } };

void dijkstra(int s) { priority_queue<data> st; FOR(i,1,n) d[s][i] = inf; d[s][s] = 0; st.push({s, d[s][s]}); while (! st.empty()) { int u = st.top().u, c = st.top().c; st.pop(); if (c > d[s][u]) continue; for (auto k : a[u]) { int v = k.X, w = k.Y; if (d[s][v] > d[s][u] + w) { d[s][v] = d[s][u] + w; st.push({v, d[s][v]}); } } } }

int main() { // freopen("INP.TXT", "r", stdin); // freopen("OUT.TXT", "w", stdout);

Copy
scanf("%d%d", &n,&m); FOR(i,1,m) scanf("%d", &f[i]); FOR(u,1,n) { FOR(v,1,n) { int c; scanf("%d", &c); if (u == v) continue; a[u].pb({v,c}); } } FOR(s,1,n) dijkstra(s); f[0] = 1; f[++m] = n; ll ans = 0ll; FOR(i,0,m-1) ans += d [ f[i] ] [ f[i+1] ]; printf("%lld\n", ans); return 0;

}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6
nguyenthihai14121980 đã bình luận 3:08:52 ch, 25/07/2024
define Y second

define pb push_back

define mp make_pair

define ep emplace_back

define EL printf("\n")

define sz(A) (int) A.size()

define FOR(i,l,r) for (int i=l;i<=r;i++)

define FOD(i,r,l) for (int i=r;i>=l;i--)

define fillchar(a,x) memset(a, x, sizeof (a))

define faster iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 101, inf = 1e9; int n, m, d[N][N], f[10002]; vector<ii> a[N];

struct data { int u, c; bool operator < (const data &o) const { return c > o.c; } };

void dijkstra(int s) { priority_queue<data> st; FOR(i,1,n) d[s][i] = inf; d[s][s] = 0; st.push({s, d[s][s]}); while (! st.empty()) { int u = st.top().u, c = st.top().c; st.pop(); if (c > d[s][u]) continue; for (auto k : a[u]) { int v = k.X, w = k.Y; if (d[s][v] > d[s][u] + w) { d[s][v] = d[s][u] + w; st.push({v, d[s][v]}); } } } }

int main() { // freopen("INP.TXT", "r", stdin); // freopen("OUT.TXT", "w", stdout);

Copy
scanf("%d%d", &n,&m); FOR(i,1,m) scanf("%d", &f[i]); FOR(u,1,n) { FOR(v,1,n) { int c; scanf("%d", &c); if (u == v) continue; a[u].pb({v,c}); } } FOR(s,1,n) dijkstra(s); f[0] = 1; f[++m] = n; ll ans = 0ll; FOR(i,0,m-1) ans += d [ f[i] ] [ f[i+1] ]; printf("%lld\n", ans); return 0;

}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.