4846

#include <iostream>
#include <cmath>
using namespace std;

int main() {
double x1, x2, y1, y2;
cin >> x1 >> y1;
double sum = 0;
while (cin >> x1 >> y1 >> x2 >> y2) {
double dx = x1 - x2;
double dy = y1 - y2;
sum += sqrt(dx * dx + dy * dy) * 2;
}
int minutes = round(sum / 1000 / 20 * 60);
int hours = minutes / 60;
minutes %= 60;

printf("%d:%02d", hours, minutes);
return 0;
}


#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010, M = 10010;

struct Ver {
int id, type, dist;
bool operator > (const Ver &t) const {
return dist > t.dist;
}
};
int n, m, S, T;
int h[N], e[M], ne[M], w[M], idx = 0;
int dist[N][2], cnt[N][2];
bool st[N][2];

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

int dijkstra() {
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
memset(cnt, 0, sizeof cnt);
dist[S][0] = 0, cnt[S][0] = 1;
priority_queue<Ver, vector<Ver>, greater<Ver>> heap;
heap.push({S, 0, 0});

while (heap.size()) {
Ver t = heap.top();
heap.pop();

int ver = t.id, type = t.type, distance = t.dist, count = cnt[ver][type];
if (st[ver][type]) continue;
st[ver][type] = true;

for (int i = h[ver]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j][0] > distance + w[i]) {
dist[j][1] = dist[j][0];
cnt[j][1] = cnt[j][0];
heap.push({j, 1, dist[j][1]});
dist[j][0] = distance + w[i];
cnt[j][0] = count;
heap.push({j, 0, dist[j][0]});
}
else if (dist[j][0] == distance + w[i]) {
cnt[j][0] += count;
}
else if (dist[j][1] > distance + w[i]) {
dist[j][1] = distance + w[i];
cnt[j][1] = count;
heap.push({j, 1, dist[j][1]});
}
else if (dist[j][1] == distance + w[i]) {
cnt[j][1] += count;
}
}
}
int res = cnt[T][0];
if (dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];
return res;
}

int main() {
int cases;
cin >> cases;
while (cases -- ) {
memset(h, -1, sizeof h);
idx = 0;
scanf("%d%d", &n, &m);
while ( m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}
scanf("%d%d", &S, &T);
printf("%d\n", dijkstra());
}
return 0;
}



#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 4e5 + 10;
const int mod = 100003;

int n, m;
int h[N], e[M], ne[M], idx = 0;
int dist[N], cnt[N];
int q[N];
bool st[N];

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

void bfs() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
cnt[1] = 1;
int hh = 0, tt = 0;
q[0] = 1;
while (hh <= tt) {
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + 1) {
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
q[ ++ tt ] = j;
}
else if (dist[j] == dist[t] + 1) {
cnt[j] = (cnt[j] + cnt[t]) % mod;
}
}
}
}

int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while ( m -- ) {
int a, b;
scanf("%d%d", &a, &b);
}
bfs();
for (int i = 1; i <= n; i ++ ) printf("%d\n", cnt[i]);
return 0;
}


#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010, INF = 0x3f3f3f3f;

int n, m, T;
int h[N], e[M], ne[M], w[M], idx = 0;
int dist[N], q[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() {
int scnt;
cin >> scnt;
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
int hh = 0, tt = 0;
while (scnt -- ) {
int u;
scanf("%d", &u);
q[tt ++ ] = u;
dist[u] = 0;
st[u] = true;
}
while (hh != tt) {
int t = q[hh ++ ];
if (hh == N) hh = 0;
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[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}

int main() {
while (scanf("%d%d%d", &n, &m, &T) != -1) {
memset(h, -1, sizeof h);
idx = 0;
while ( m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}
spfa();
if (dist[T] == INF) puts("-1");
else printf("%d\n", dist[T]);
}
return 0;
}


#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
const int M = 10000 + 10000 + 1000 + 10;
const int INF = 0x3f3f3f3f;

int n, m1, m2;
int dist[N];
int h[N], e[M], w[M], ne[M], idx = 0;
int q[N], cnt[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 ++ ;
}

bool spfa(int size) {
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
memset(cnt, 0, sizeof cnt);
int hh = 0, tt = 0;
for (int i = 1; i <= size; i ++ ) {
q[tt ++ ] = i;
st[i] = true;
dist[i] = 0;
}
while (hh != tt) {
int t = q[hh ++ ];
if (hh == N) hh = 0;
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[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return false;
}

int main() {
cin >> n >> m1 >> m2;
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++ ) add(i + 1, i, 0);
while ( m1 -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (b < a) swap(a, b);
}
while ( m2 -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (b < a) swap(a, b);
}
if (spfa(n)) puts("-1");
else {
spfa(1);
if (dist[n] == INF) puts("-2");
else printf("%d\n", dist[n]);
}
return 0;
}


#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010;
const int M = 150010;

int n;
int h[N], e[M], ne[M], w[M], idx = 0;
int dist[N];
int q[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(dist, -0x3f, sizeof dist);
dist[0] = 0;
int hh = 0, tt = 1;
q[0] = 0, st[0] = true;

while ( hh != tt ) {
int t = q[hh ++ ];
st[t] = false;
if (hh == N) hh = 0;
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]) {
st[j] = true;
q[tt ++ ] = j;
if (tt == N) tt = 0;
}
}
}
}
}

int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i < N; i ++ ) {
}

while ( n -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a ++ , b ++ ;
}
spfa();
cout << dist[50001] << endl;
return 0;
}


#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10;
typedef long long LL;

int n, m;
int h[N], e[M], ne[M], w[M], idx = 0;
int q[N], cnt[N];
bool st[N];
LL dist[N];

void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
/*
bool spfa() {
int hh = 0, tt = 1;
memset(dist, -0x3f, sizeof dist);
dist[0] = 0, q[0] = 0;
st[0] = true;

while (hh != tt) {
int t = q[hh ++ ];
st[t] = false;
if (hh == N) hh = 0;
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 + 1) return true;
if (!st[j]) {
st[j] = true;
q[tt ++ ] = j;
if (tt == N) tt = 0;
}
}
}
}
return false;
}*/

bool spfa() {
memset(dist, -0x3f, sizeof dist);
dist[0] = 0;
int hh = 0, tt = 1;
q[0] = 0, st[0] = true;
while ( hh != tt ) {
int t = q[ -- tt ];
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 + 1) return true;
if (!st[j]) {
q[tt ++ ] = j;
st[j] = true;
}
}
}
}
return false;
}

int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while ( m -- ) {
int x, a, b;
scanf("%d%d%d", &x, &a, &b);
else if (x == 2) add(a, b, 1);
else if (x == 3) add(b, a, 0);
else if (x == 4) add(b, a, 1);
}
for (int i = 1; i <= n; i ++ ) add(0, i, 1);
if (spfa()) puts("-1");
else {
LL res = 0;
for (int i = 1; i <= n; i ++ ) res += dist[i];
printf("%lld\n", res);
}
return 0;
}


#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = N * N, K = N * N * 2;

int n, m, k;
int idx[N][N];
struct Edge {
int a, b, w;
} e[K];
int p[M];

int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}

void get_edges() {
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 01 -1};
int dw[4] = {1, 2, 1, 2};
for (int z = 0; z < 2; z ++ ) {
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
for (int u = 0; u < 4; u ++ ) {
if (u % 2 == z) {
int x = i + dx[u], y = j + dy[u], w = dw[u];
if (x && y && x <= n && y <= m) {
int a = idx[i][j], b = idx[x][y];
if (a < b) e[k ++ ] = {a, b, w};
}
}
}
}
}
}
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n * m; i ++ ) p[i] = i;
for (int i = 1, t = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ , t ++ ) {
idx[i][j] = t;
}
}
int x1, y1, x2, y2;
while (cin >> x1 >> y1 >> x2 >> y2) {
int a = idx[x1][y1], b = idx[x2][y2];
p[find(a)] = find(b);
}
get_edges();
int res = 0;
for (int i = 0; i < k; i ++ ) {
int a = find(e[i].a), b = find(e[i].b);
if (a != b) {
p[a] = b;
res += e[i].w;
}
}
cout << res << endl;
return 0;
}


#include <iostream>
#include <algorithm>
using namespace std;
const int M = 10010;
const int N = 2010;
struct Edge {
int a, b, w;
bool operator < (const Edge &t) const {
return w < t.w;
}
}e[M];

int n, m;
int p[N];

int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) p[i] = i;
int res = 0, k = 0;
while ( m -- ) {
int t, a, b, w;
cin >> t >> a >> b >> w;
if (t == 1) {
p[find(a)] = find(b);
res += w;
}
else e[k ++ ] = {a, b, w};
}
sort(e, e + k);
for (int i = 0; i < k; i ++ ) {
int a = find(e[i].a), b = find(e[i].b);
if (a != b) {
p[a] = b;
res += e[i].w;
}
}
cout << res << endl;
return 0;
}


#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
const int M = 10010;

int n, m;
struct Edge {
int a, b, w;
bool operator < (const Edge &t) const {
return w < t.w;
}
} e[M];

int p[N];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 0; i < m; i ++ ) {
int a, b, w;
cin >> a >> b >> w;
e[i] = {a, b, w};
}
sort(e, e + m);
int res = 0;
for (int i = 0; i < m; i ++ ) {
int a = find(e[i].a), b = find(e[i].b);
if (a != b) {
p[a] = b;
res = e[i].w;
}
}
cout << n - 1 << " " << res << endl;
return 0;
}