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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define INF (0x7ffffff)
#define pii pair<int, int>
using namespace std;
struct edg
{
int from, to, next, cost;
}b[MAXM << 1], rb[MAXM];
struct cmp
{
bool operator () (const pii x, const pii y)
{ return x.second > y.second; }
};
int g[MAXN], cntb, n, m, pre[MAXN], dis[MAXN], deep[MAXN];
bool vis[MAXN];
priority_queue<pii, vector<pii>, cmp> q;
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from, b[cntb].to = to, b[cntb].cost = cost;
g[from] = cntb;
}
void dijk()
{
memset(vis, false, sizeof(vis));
memset(dis, 0x7f, sizeof(dis));
q.push(make_pair(1, dis[1] = 0));
deep[1] = 1;
while (!q.empty())
{
pii dq = q.top();
q.pop();
if (vis[dq.first])
continue;
vis[dq.first] = true;
for (int i = g[dq.first]; i; i = b[i].next)
if (dis[b[i].to] > dq.second + b[i].cost)
{
dis[b[i].to] = dq.second + b[i].cost;
pre[b[i].to] = dq.first;
deep[b[i].to] = deep[dq.first] + 1;
q.push(make_pair(b[i].to, dis[b[i].to]));
}
}
}
bool cmp1(edg x, edg y)
{ return x.cost < y.cost; }
void solve(edg e)
{
int x = e.from, y = e.to;
while (x != y)
{
if (deep[x] < deep[y])
swap(x, y);
if (!vis[x])
dis[x] = e.cost - dis[x];
vis[x] = true;
x = pre[x];
}
while (e.from != x)
{
int bf = e.from;
e.from = pre[e.from];
pre[bf] = x;
}
while (e.to != x)
{
int be = e.to;
e.to = pre[e.to];
pre[be] = x;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &rb[i].from, &rb[i].to, &rb[i].cost);
adn(rb[i].from, rb[i].to, rb[i].cost);
adn(rb[i].to, rb[i].from, rb[i].cost);
}
dijk();
for (int i = 1; i <= m; i++)
if (dis[rb[i].from] < INF)
rb[i].cost += dis[rb[i].from] + dis[rb[i].to];
else
rb[i].cost = INF;
sort(rb + 1, rb + m + 1, cmp1);
memset(vis, false, sizeof(vis));
for (int i = 1; i <= m; i++)
if (dis[rb[i].from] < INF && pre[rb[i].to] != rb[i].from && pre[rb[i].from] != rb[i].to)
solve(rb[i]);
for (int i = 2; i <= n; i++)
if (dis[i] < INF && vis[i])
printf("%d\n", dis[i]);
else
puts("-1");
return 0;
}
|
