关键结点

一个含有 n n n个结点 m m m条边的无向有权图，判断每个结点是否在从 1 1 1到 n n n的最短路径上

输入描述
第一行输入一个整数 T T T，代表有 T T T组测试数据 对于每一组测试数据，第一行有 2 2 2个整数 n , m n,m n,m，接下来 m m m行每行有 3 3 3个整数 x i , y i , w i x_i,y_i,w_i xi​,yi​,wi​x ，表示 x x x和 y y y之间有一条权值为 w i w_i wi​ 的边

输出描述
对于每组测试数据，在一行中输出 n n n个整数，第 i i i个整数代表 i i i号结点的关键性
0 0 0代表该结点不可能出现在从 1 1 1到 n n n的最短路径上
1 1 1代表该结点出现在所有从 1 1 1到 n n n的最短路径上
2 2 2代表该结点出现在部分从 1 1 1到 n n n的最短路径上

数据范围
1 ≤ T ≤ 1000 1≤T≤1000 1≤T≤1000
2 ≤ n ≤ 1000 2≤n≤1000 2≤n≤1000
n − 1 ≤ m ≤ min ⁡ ( n × ( n − 1 ) 2 , 2 ⋅ 10 5 ) n-1≤m≤\min(\dfrac{n\times(n-1)}{2}, 2\cdot{10}^5) n−1≤m≤min(2n×(n−1)​,2⋅105)
1 ≤ w i ≤ 1 0 8 1≤w_i≤10^8 1≤wi​≤108
∑ n ≤ 2 ⋅ 10 5 \sum{n}≤2\cdot{10}^5 ∑n≤2⋅105
∑ m ≤ 2 ⋅ 10 5 \sum{m}≤2\cdot{10}^5 ∑m≤2⋅105
保证无重边无自环且连通

输出时每行末尾的多余空格，不影响答案正确性

样例输入
2
6 7
1 2 1
2 3 1
2 4 1
2 5 2
3 5 1
4 5 2
5 6 1
4 6
1 2 1
1 3 1
1 4 2
2 3 1
2 4 1
3 4 1
样例输出
1 1 2 0 1 1
1 2 2 1

样例解释
对于第一组样例的解释：

对于第二组样例的解释：

红点表示一定不在最短路径上 绿点表示在所有最短路径上 蓝点表示在一部分最短路径上

分别从节点 1 1 1和 n n n求单元最短路，得到每个点到节点 1 1 1和 n n n的最距离 d 1 d1 d1， d 2 d2 d2。
设 a n s [ i ] ans[i] ans[i]存储 i i i号节点的类型，初始化为0。
对于任意一边 e x , y e_{x,y} ex,y​，满足 d 1 [ x ] < d 1 [ y ] d1[x]<d1[y] d1[x]<d1[y]且 d 1 [ x ] + d x , y + d 2 [ y ] = a 1 [ n ] d1[x]+d_{x,y}+d2[y]=a1[n] d1[x]+dx,y​+d2[y]=a1[n]，则该边在最短路径上，因此令 a n s [ x ] = a n s [ y ] = 2 ans[x]=ans[y]=2 ans[x]=ans[y]=2。
将所有此类边建图，在该图上求割点，令割点 i i i： a n s [ i ] = 1 ans[i]=1 ans[i]=1。
最后要单独令 a n s [ 1 ] = a n s [ n ] = 1 ans[1]=ans[n]=1 ans[1]=ans[n]=1。
求最短路复杂度为 O ( n l o g m ) O(nlogm) O(nlogm)，Tarjan求割点复杂度为 O ( n ) O(n) O(n)，因此总体时间复杂度为 O ( n l o g m ) O(nlogm) O(nlogm)。

#include<bits/stdc++.h>#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define sc(a) scahf("%c",&a);
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define repd(i, a, b) for(register int i=a;i>=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pii pair<int,int>
#define mii unordered_map<int,int>
#define msi unordered_map<string,int>
#define lowbit(x) ((x)&(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;inline int qr() {int f = 0, fu = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')fu = -1;c = getchar();}while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + c - 48;c = getchar();}return f * fu;
}const int N = 1e3 + 10, M = 2e5 + 10;
int head[N], ver[M << 1], Next[M << 1], edge[M << 1], tot;
int n, m, T, dfn[N], low[N], num, ans[N];
ll d1[N], d2[N];
bool v[N];
int hc[N], vc[M << 1], nc[M << 1], tc;inline void add(int x, int y, int z) {ver[++tot] = y;Next[tot] = head[x];edge[tot] = z;head[x] = tot;
}inline void add_c(int x, int y) {vc[++tc] = y;nc[tc] = hc[x];hc[x] = tc;
}inline void dijkstra1() {repi(i, 1, n)v[i] = false, d1[i] = 4e18;d1[1] = 0;priority_queue<pair<ll, int> > q;q.push(make_pair(0, 1));while (!q.empty()) {int x = q.top().second;q.pop();if (v[x]) continue;v[x] = true;reps(x) {int y = ver[i], z = edge[i];if (d1[y] > d1[x] + z) {d1[y] = d1[x] + z;q.push(make_pair(-d1[y], y));}}}
}inline void dijkstra2() {repi(i, 1, n)v[i] = false, d2[i] = 4e18;d2[n] = 0;priority_queue<pair<ll, int> > q;q.push(make_pair(0, n));while (!q.empty()) {int x = q.top().second;q.pop();if (v[x]) continue;v[x] = true;reps(x) {int y = ver[i], z = edge[i];if (d2[y] > d2[x] + z) {d2[y] = d2[x] + z;q.push(make_pair(-d2[y], y));}}}
}inline void build() {for (int i = 1; i < tot; i += 2) {int x = ver[i], y = ver[i + 1], z = edge[i];if (d1[x] > d1[y])swap(x, y);if (d1[x] + z + d2[y] == d1[n])add_c(x, y), add_c(y, x), ans[x] = ans[y] = 2;}
}void tarjan(int x) {dfn[x] = low[x] = ++num;int flag = 0;for (int i = hc[x]; i; i = nc[i]) {int y = vc[i];if (!dfn[y]) {tarjan(y);low[x] = min(low[x], low[y]);if (low[y] >= dfn[x]) {flag++;if (x != 1 || flag > 1)ans[x] = 1;}} else low[x] = min(low[x], dfn[y]);}
}int main() {T = qr();while (T--) {n = qr(), m = qr();repi(i, 1, n)head[i] = 0;tot = 0;while (m--) {int x = qr(), y = qr(), z = qr();add(x, y, z), add(y, x, z);}dijkstra1(), dijkstra2();repi(i, 1, n)hc[i] = ans[i] = dfn[i] = low[i] = 0;tc = num = 0;build();tarjan(1);ans[n] = ans[1] = 1;repi(i, 1, n)printf("%d%c", ans[i], ce(i, n));}return 0;
}

关键结点

一个含有 n n n个结点 m m m条边的无向有权图，判断每个结点是否在从 1 1 1到 n n n的最短路径上

输入描述
第一行输入一个整数 T T T，代表有 T T T组测试数据 对于每一组测试数据，第一行有 2 2 2个整数 n , m n,m n,m，接下来 m m m行每行有 3 3 3个整数 x i , y i , w i x_i,y_i,w_i xi​,yi​,wi​x ，表示 x x x和 y y y之间有一条权值为 w i w_i wi​ 的边

输出描述
对于每组测试数据，在一行中输出 n n n个整数，第 i i i个整数代表 i i i号结点的关键性
0 0 0代表该结点不可能出现在从 1 1 1到 n n n的最短路径上
1 1 1代表该结点出现在所有从 1 1 1到 n n n的最短路径上
2 2 2代表该结点出现在部分从 1 1 1到 n n n的最短路径上

数据范围
1 ≤ T ≤ 1000 1≤T≤1000 1≤T≤1000
2 ≤ n ≤ 1000 2≤n≤1000 2≤n≤1000
n − 1 ≤ m ≤ min ⁡ ( n × ( n − 1 ) 2 , 2 ⋅ 10 5 ) n-1≤m≤\min(\dfrac{n\times(n-1)}{2}, 2\cdot{10}^5) n−1≤m≤min(2n×(n−1)​,2⋅105)
1 ≤ w i ≤ 1 0 8 1≤w_i≤10^8 1≤wi​≤108
∑ n ≤ 2 ⋅ 10 5 \sum{n}≤2\cdot{10}^5 ∑n≤2⋅105
∑ m ≤ 2 ⋅ 10 5 \sum{m}≤2\cdot{10}^5 ∑m≤2⋅105
保证无重边无自环且连通

输出时每行末尾的多余空格，不影响答案正确性

样例输入
2
6 7
1 2 1
2 3 1
2 4 1
2 5 2
3 5 1
4 5 2
5 6 1
4 6
1 2 1
1 3 1
1 4 2
2 3 1
2 4 1
3 4 1
样例输出
1 1 2 0 1 1
1 2 2 1

样例解释
对于第一组样例的解释：

对于第二组样例的解释：

红点表示一定不在最短路径上 绿点表示在所有最短路径上 蓝点表示在一部分最短路径上

分别从节点 1 1 1和 n n n求单元最短路，得到每个点到节点 1 1 1和 n n n的最距离 d 1 d1 d1， d 2 d2 d2。
设 a n s [ i ] ans[i] ans[i]存储 i i i号节点的类型，初始化为0。
对于任意一边 e x , y e_{x,y} ex,y​，满足 d 1 [ x ] < d 1 [ y ] d1[x]<d1[y] d1[x]<d1[y]且 d 1 [ x ] + d x , y + d 2 [ y ] = a 1 [ n ] d1[x]+d_{x,y}+d2[y]=a1[n] d1[x]+dx,y​+d2[y]=a1[n]，则该边在最短路径上，因此令 a n s [ x ] = a n s [ y ] = 2 ans[x]=ans[y]=2 ans[x]=ans[y]=2。
将所有此类边建图，在该图上求割点，令割点 i i i： a n s [ i ] = 1 ans[i]=1 ans[i]=1。
最后要单独令 a n s [ 1 ] = a n s [ n ] = 1 ans[1]=ans[n]=1 ans[1]=ans[n]=1。
求最短路复杂度为 O ( n l o g m ) O(nlogm) O(nlogm)，Tarjan求割点复杂度为 O ( n ) O(n) O(n)，因此总体时间复杂度为 O ( n l o g m ) O(nlogm) O(nlogm)。

#include<bits/stdc++.h>#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define sc(a) scahf("%c",&a);
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define repd(i, a, b) for(register int i=a;i>=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pii pair<int,int>
#define mii unordered_map<int,int>
#define msi unordered_map<string,int>
#define lowbit(x) ((x)&(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;inline int qr() {int f = 0, fu = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')fu = -1;c = getchar();}while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + c - 48;c = getchar();}return f * fu;
}const int N = 1e3 + 10, M = 2e5 + 10;
int head[N], ver[M << 1], Next[M << 1], edge[M << 1], tot;
int n, m, T, dfn[N], low[N], num, ans[N];
ll d1[N], d2[N];
bool v[N];
int hc[N], vc[M << 1], nc[M << 1], tc;inline void add(int x, int y, int z) {ver[++tot] = y;Next[tot] = head[x];edge[tot] = z;head[x] = tot;
}inline void add_c(int x, int y) {vc[++tc] = y;nc[tc] = hc[x];hc[x] = tc;
}inline void dijkstra1() {repi(i, 1, n)v[i] = false, d1[i] = 4e18;d1[1] = 0;priority_queue<pair<ll, int> > q;q.push(make_pair(0, 1));while (!q.empty()) {int x = q.top().second;q.pop();if (v[x]) continue;v[x] = true;reps(x) {int y = ver[i], z = edge[i];if (d1[y] > d1[x] + z) {d1[y] = d1[x] + z;q.push(make_pair(-d1[y], y));}}}
}inline void dijkstra2() {repi(i, 1, n)v[i] = false, d2[i] = 4e18;d2[n] = 0;priority_queue<pair<ll, int> > q;q.push(make_pair(0, n));while (!q.empty()) {int x = q.top().second;q.pop();if (v[x]) continue;v[x] = true;reps(x) {int y = ver[i], z = edge[i];if (d2[y] > d2[x] + z) {d2[y] = d2[x] + z;q.push(make_pair(-d2[y], y));}}}
}inline void build() {for (int i = 1; i < tot; i += 2) {int x = ver[i], y = ver[i + 1], z = edge[i];if (d1[x] > d1[y])swap(x, y);if (d1[x] + z + d2[y] == d1[n])add_c(x, y), add_c(y, x), ans[x] = ans[y] = 2;}
}void tarjan(int x) {dfn[x] = low[x] = ++num;int flag = 0;for (int i = hc[x]; i; i = nc[i]) {int y = vc[i];if (!dfn[y]) {tarjan(y);low[x] = min(low[x], low[y]);if (low[y] >= dfn[x]) {flag++;if (x != 1 || flag > 1)ans[x] = 1;}} else low[x] = min(low[x], dfn[y]);}
}int main() {T = qr();while (T--) {n = qr(), m = qr();repi(i, 1, n)head[i] = 0;tot = 0;while (m--) {int x = qr(), y = qr(), z = qr();add(x, y, z), add(y, x, z);}dijkstra1(), dijkstra2();repi(i, 1, n)hc[i] = ans[i] = dfn[i] = low[i] = 0;tc = num = 0;build();tarjan(1);ans[n] = ans[1] = 1;repi(i, 1, n)printf("%d%c", ans[i], ce(i, n));}return 0;
}