题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2874
这题有不连通的情况，特别注意。
觉得是存query的姿势不对，用前向星存了一遍，还是T……
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%lld", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a))
#define lp p << 1
#define rp p << 1 | 1
#define pi 3.14159265359
#define RT return
#define lowbit(x) x & (-x)
#define onenum(x) __builtin_popcount(x)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; typedef struct Query {
int idx;
int u, v;
Query() {}
Query(int uu, int vv, int ii) : u(uu), v(vv), idx(ii) {}
}Query; typedef struct Edge {
int u, v, w, idx;
int next;
Edge() {}
Edge(int uu, int vv, int ww) : u(uu), v(vv), w(ww) {}
}Edge; typedef struct Ans {
int idx;
int ans;
Ans() {}
Ans(int aa, int ii) :ans(aa), idx(ii) {}
}Ans; const int maxn = ;
const int maxm = ;
int n, m, c, qcnt;
int depth[maxn];
bool vis[maxn];
int pre[maxn];
Ans ans[maxm];
Edge edge[maxn];
Edge q[maxm];
Query qq[maxm];
int qhead[maxm];
int head[maxn];
int ecnt;
int u, v, w; void adde(int u, int v, int w) {
edge[ecnt].u = u;
edge[ecnt].v = v;
edge[ecnt].w = w;
edge[ecnt].next = head[u];
head[u] = ecnt++;
} void addq(int u, int v, int i) {
q[qcnt].u = u;
q[qcnt].v = v;
q[qcnt].idx = i;
q[qcnt].next = qhead[u];
qhead[u] = ecnt++;
} int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
} void unite(int x, int y) {
x = find(x);
y = find(y);
if(x != y) pre[y] = x;
} void dfs(int u, int p, int d) {
depth[u] = d;
for(int i = head[u]; ~i; i=edge[i].next) {
int v = edge[i].v;
if(!vis[v] && v != p) {
dfs(v, u, d+edge[i].w);
unite(u, v);
}
}
vis[u] = ;
for(int i = qhead[u]; ~i; i=q[i].next) {
int uu = q[i].u;
int vv = q[i].v;
int idx = q[i].idx;
if((vis[vv] && uu == u) || (vis[uu] && vv == u)) {
ans[idx].ans = depth[vv] + depth[uu];
}
}
} bool cmp(Ans x, Ans y) {
return x.idx < y.idx;
} int ufs[maxn]; int find1(int x) {
return ufs[x] == x ? x : ufs[x] = find1(ufs[x]);
} void unite1(int x, int y) {
x = find1(x);
y = find1(y);
if(x != y) ufs[y] = x;
} inline bool scan_d(int &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<''||in>'')) in=getchar();
if(in=='-'){ IsN=true;num=;}
else num=in-'';
while(in=getchar(),in>=''&&in<=''){
num*=,num+=in-'';
}
if(IsN) num=-num;
return true;
} int main() {
// FRead();
while(~scanf("%d%d%d",&n,&m,&c)) {
Cls(vis); Cls(depth); Cls(ans); Clr(head, -); Clr(qhead, -);
qcnt = ; Rep(i, n+) pre[i] = i, ufs[i] = i;
Rep(i, m) {
scan_d(u); scan_d(v); scan_d(w);
adde(u, v, w); adde(v, u, w);
unite1(u, v);
}
Rep(i, c) {
scan_d(u); scan_d(v);
addq(u, v, i);
qq[i] = Query(u, v, i);
}
For(i, , n+) if(!vis[i]) dfs(i, -, );
Rep(i, c) {
if(find1(qq[ans[i].idx].u) != find1(qq[ans[i].idx].v)) puts("Not connected");
else printf("%d\n", ans[i].ans);
}
}
RT ;
}
……TARJAN也T了……
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%lld", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a))
#define lp p << 1
#define rp p << 1 | 1
#define pi 3.14159265359
#define RT return
#define lowbit(x) x & (-x)
#define onenum(x) __builtin_popcount(x)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; typedef struct Query {
int idx;
int u, v;
Query() {}
Query(int uu, int vv, int ii) : u(uu), v(vv), idx(ii) {}
}Query; typedef struct Edge {
int u, v, w;
int next;
Edge() {}
Edge(int uu, int vv, int ww) : u(uu), v(vv), w(ww) {}
}Edge; typedef struct Ans {
int idx;
int ans;
Ans() {}
Ans(int aa, int ii) :ans(aa), idx(ii) {}
}Ans; const int maxn = ;
const int maxm = ;
int n, m, c, qcnt;
int depth[maxn];
bool vis[maxn];
int pre[maxn];
Query q[maxm];
Ans ans[maxm];
Edge edge[maxn];
int head[maxn];
int ecnt;
int u, v, w; void adde(int u, int v, int w) {
edge[ecnt].u = u;
edge[ecnt].v = v;
edge[ecnt].w = w;
edge[ecnt].next = head[u];
head[u] = ecnt++;
} int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
} void unite(int x, int y) {
x = find(x);
y = find(y);
if(x != y) pre[y] = x;
} void dfs(int u, int p, int d) {
depth[u] = d;
for(int i = head[u]; ~i; i=edge[i].next) {
int v = edge[i].v;
if(!vis[v] && v != p) {
dfs(v, u, d+edge[i].w);
unite(u, v);
}
}
vis[u] = ;
Rep(i, qcnt) {
int uu = q[i].u;
int vv = q[i].v;
int idx = q[i].idx;
if((vis[vv] && uu == u) || (vis[uu] && vv == u)) {
ans[idx].idx = idx;
ans[idx].ans = depth[vv] + depth[uu];
}
}
} bool cmp(Ans x, Ans y) {
return x.idx < y.idx;
} int ufs[maxn]; int find1(int x) {
return ufs[x] == x ? x : ufs[x] = find1(ufs[x]);
} void unite1(int x, int y) {
x = find1(x);
y = find1(y);
if(x != y) ufs[y] = x;
} inline bool scan_d(int &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<''||in>'')) in=getchar();
if(in=='-'){ IsN=true;num=;}
else num=in-'';
while(in=getchar(),in>=''&&in<=''){
num*=,num+=in-'';
}
if(IsN) num=-num;
return true;
} int main() {
// FRead();
while(~scanf("%d%d%d",&n,&m,&c)) {
Cls(vis); Cls(depth); Cls(ans); Clr(head, -);
qcnt = ; Rep(i, n+) pre[i] = i, ufs[i] = i;
Rep(i, m) {
scan_d(u); scan_d(v); scan_d(w);
adde(u, v, w); adde(v, u, w);
unite1(u, v);
}
Rep(i, c) {
scan_d(u); scan_d(v);
q[qcnt++] = Query(u, v, i);
}
For(i, , n+) if(!vis[i]) dfs(i, -, );
Rep(i, c) {
if(find1(q[ans[i].idx].u) != find1(q[ans[i].idx].v)) puts("Not connected");
else printf("%d\n", ans[i].ans);
}
}
RT ;
}
在线胡搞T了，等下写个离线的。
TLE代码：
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%I64d", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a))
#define pi 3.14159265359
#define RT return
#define lowbit(x) x & (-x)
#define onenum(x) __builtin_popcount(x)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; typedef struct Edge {
int u, v, w;
int next;
}Edge;
const int maxn = ;
const int maxm = ;
int n, m, c;
int depth[maxn], fa[maxn];
int pre[maxn];
Edge edge[maxm];
int head[maxn];
int ecnt;
bool vis[maxn]; void adde(int u, int v, int w) {
edge[ecnt].u = u;
edge[ecnt].v = v;
edge[ecnt].w = w;
edge[ecnt].next = head[u];
head[u] = ecnt++;
} int find(int x) {
x == pre[x] ? x : pre[x] = find(pre[x]);
} void unite(int x, int y) {
x = find(x);
y = find(y);
if(x != y) pre[y] = x;
} void dfs(int u, int p, int d) {
vis[u] = ;
depth[u] = d; fa[u] = p;
for(int i = head[u]; ~i; i=edge[i].next) {
int v = edge[i].v;
int w = edge[i].w;
if(!vis[v]) dfs(v, u, d+w);
}
} int lca(int u, int v) {
int s = ;
while(depth[u] > depth[v]) {
s += depth[u];
u = pre[u];
}
while(depth[v] > depth[u]) {
s += depth[v];
v = pre[v];
}
while(u != v) {
s += (depth[u] + depth[v]);
u = pre[u];
v = pre[v];
}
return s;
} inline bool scan_d(int &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<''||in>'')) in=getchar();
if(in=='-'){ IsN=true;num=;}
else num=in-'';
while(in=getchar(),in>=''&&in<=''){
num*=,num+=in-'';
}
if(IsN) num=-num;
return true;
} int main() {
FRead();
int u, v, w;
while(~scanf("%d%d%d",&n,&m,&c)) {
Clr(head, -); ecnt = ;
Rep(i, n+) pre[i] = i;
Rep(i, m) {
scan_d(u); scan_d(v); scan_d(w);
adde(u, v, w); adde(v, u, w);
unite(u, v);
}
For(i, , n+) {
if(!vis[i]) {
dfs(i, -, );
}
}
W(c) {
scan_d(u); scan_d(v);
if(find(u) != find(v)) puts("Not connected");
else printf("%d\n", lca(u, v));
}
}
RT ;
}