fangy

3985

CODE_HUNTER

qj

Donlonboy_5
Ferrynan

yxc的小迷妹
wcyyyooo

Garfy
szn419

Chongyu
Updater

-浪漫主义狗-

RKTHlr

fangy
2天前
#include <iostream>

using namespace std;

const int N = 410, INF = 1e9;

int n, m;
int d1[N][N], d2[N][N];

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

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
if (i == j) d1[i][j] = d2[i][j] = 0;
else d1[i][j] = INF, d2[i][j] = 1;
}

while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
d1[a][b] = d1[b][a] = 1;
d2[a][b] = d2[b][a] = INF;
}

for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
d1[i][j] = min(d1[i][j], d1[i][k] + d1[k][j]),
d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);

int res = max(d1[1][n], d2[1][n]);
if (res > INF / 2) res = -1;

cout << res << endl;

return 0;
}


fangy
3天前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = 20010, INF = 1e9;

int n, m, q;
int dist[N][N];

void floyd()
{
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 main()
{
cin >> n >> m >> q;

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) dist[i][j] = 0;
else dist[i][j] = INF;

while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
dist[a][b] = min(dist[a][b], c);
}

floyd();

while (q--)
{
int a, b;
scanf("%d%d", &a, &b);

if (dist[a][b] > INF / 2) puts("impossible");
else printf("%d\n", dist[a][b]);
}

return 0;
}


fangy
3天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];
bool used[N];

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

bool spfa()
{
queue<int> q;
for (int i = 1; i <= n; ++i) q.push(i), st[i] = 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 (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] == n) return true;
if (!st[j]) q.push(j), st[j] = true;
}
}
}
return false;
}

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

memset(h, -1, sizeof h);

while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}

if (spfa()) puts("Yes");
else puts("No");

return 0;
}


fangy
3天前
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

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

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

queue<int> q;
q.push(1);

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 (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) q.push(j), st[j] = true;
}
}
}
}

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

memset(h, -1, sizeof h);

while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}

spfa();

if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else cout << dist[n] << endl;

return 0;
}


fangy
3天前
#include <iostream>
#include <queue>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];

priority_queue<PII, vector<PII>, greater<PII>> heap;

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

void dijkstra()
{
while (heap.size())
{
auto t = heap.top();
heap.pop();

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

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

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

memset(h, -1, sizeof h);

while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}

memset(dist, 0x3f, sizeof dist);

int k;
cin >> k;
while (k--)
{
int x;
scanf("%d", &x);
dist[x] = 0;
heap.push({0, x});
}

dijkstra();

int q;
cin >> q;
while (q--)
{
int x;
scanf("%d", &x);
printf("%d\n", dist[x]);
}

return 0;
}


fangy
3天前
#include <iostream>
#include <queue>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];

priority_queue<PII, vector<PII>, greater<PII>> heap;

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

void dijkstra()
{
while (heap.size())
{
auto t = heap.top();
heap.pop();

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

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

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

memset(h, -1, sizeof h);

while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}

memset(dist, 0x3f, sizeof dist);

int k;
cin >> k;
while (k--)
{
int x;
scanf("%d", &x);
dist[x] = 0;
heap.push({0, x});
}

dijkstra();

int q;
cin >> q;
while (q--)
{
int x;
scanf("%d", &x);
printf("%d\n", dist[x]);
}

return 0;
}


fangy
3天前
#include <iostream>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

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

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

while (heap.size())
{
auto tp = heap.top();
heap.pop();

int t = tp.y;
if (st[t]) continue;
st[t] = true;

for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
dist[j] = dist[t] + w[i], heap.push({dist[j], j});
}
}
}

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

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

memset(h, -1, sizeof h);

while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}

dijkstra();

if (dist[n] > 1e9) dist[n] = -1;
cout << dist[n] << endl;

return 0;
}


fangy
3天前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 100010;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

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

for (int i = 0; i < n - 1; ++i)
{
int t = 0;
for (int j = 1; j <= n; ++j)
if (!st[j] && dist[j] < dist[t])
t = j;

st[t] = true;

for (int j = 1; j <= n; ++j)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}

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

memset(g, 0x3f, sizeof g);

while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}

dijkstra();

if (dist[n] >= 1e9) dist[n] = -1;
cout << dist[n] << endl;

return 0;
}


fangy
7天前
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1010;

int n, m;
bool g[N][N];
int ind[N], q[N];
int sta[N];
bool st[N];

int toposort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; ++i)
if (!ind[i])
q[++tt] = i;

int res = 0;
while (hh <= tt)
{
int sz = tt - hh + 1;
while (sz--)
{
auto &t = q[hh++];
for (int i = 1; i <= n; ++i)
if (g[t][i])
if (--ind[i] == 0) q[++tt] = i;
}
res++;
}
return res;
}

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

for (int i = 0; i < m; ++i)
{
memset(st, 0, sizeof st);

int cnt;
scanf("%d", &cnt);
for (int j = 0; j < cnt; ++j)
{
scanf("%d", &sta[j]);
if (j > 0 && j < cnt - 1) st[sta[j]] = true;
}

for (int j = sta[0] + 1; j < sta[cnt - 1]; ++j)
if (!st[j])
for (int k = 0; k < cnt; ++k)
{
if (!g[sta[k]][j]) ind[j]++;
g[sta[k]][j] = true;
}
}

cout << toposort() << endl;

return 0;
}


fangy
7天前
#include <iostream>
#include <vector>

using namespace std;

const int N = 110;

int n;
int ind[N], q[N];
vector<int> h[N];

void toposort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; ++i)
if (!ind[i])
q[++tt] = i;

while (hh <= tt)
{
auto &t = q[hh++];
for (auto &x : h[t])
if (--ind[x] == 0)
q[++tt] = x;
}
}

int main()
{
cin >> n;

for (int i = 1; i <= n; ++i)
{
int son;
while (cin >> son && son)
h[i].push_back(son), ind[son]++;
}

toposort();

for (int i = 0; i < n; ++i) cout << q[i] << ' ';

return 0;
}