1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 66;
inline ll read()
{
int s(0), w(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
inline void put(ll x)
{
if (! x) putchar('0');
if (x < 0) putchar('-'), x = -x;
int num(0); char c[66];
while (x) c[++ num] = x % 10 + 48, x /= 10;
while (num) putchar(c[num --]);
return (void)(putchar('\n'));
}
int ver[N << 1], nex[N << 1], len[N << 1], head[N], cnt;
inline void add_edge(int x, int y, int z)
{
ver[++ cnt] = y;
nex[cnt] = head[x];
len[cnt] = z;
return (void)(head[x] = cnt);
}
int n, m, tot;
int num[N];
struct yhzhyhm
{
int a[360][360];
yhzhyhm operator * (const yhzhyhm &x) const
{
yhzhyhm c; int i, j, k;
memset(c.a, 0x3f, sizeof c.a);
for (k = 1; k <= tot; ++ k)
{
for (i = 1; i <= tot; ++ i)
{
for (j = 1; j <= tot; ++ j)
{
c.a[i][j] = min(c.a[i][j], a[i][k] + x.a[k][j]);
}
}
}
return c;
}
}dis, ans;
signed main()
{
freopen("run.in", "r", stdin), freopen("run.out", "w", stdout);
int i, x, y, z, s, t;
memset(dis.a, 0x3f, sizeof dis.a);
n = read(), m = read(), s = read(), t = read();
for (i = 1; i <= m; ++ i)
{
z = read(), x = read(), y = read();
if (! num[x]) num[x] = ++ tot;
if (! num[y]) num[y] = ++ tot;
dis.a[num[x]][num[y]] = dis.a[num[y]][num[x]] = z;
}
-- n, ans = dis;
for (; n; n >>= 1)
{
if (n & 1) ans = ans * dis;
dis = dis * dis;
}
put(ans.a[num[s]][num[t]]);
return 0;
}
|