NC51260. Freda 的传呼机
描述
输入描述
第一行包含三个用空格隔开的整数，N、M 和 Q。
接下来 M 行每行三个整数 x、y、t，表示房屋 x 和 y 之间有一条传递时间为 t 的光缆。
最后 Q 行每行两个整数 x、y，表示 Freda 想知道在 x 和 y 之间传呼最少需要多长时间。
输出描述
输出 Q 行，每行一个整数，表示 Freda 每次试验的结果。
示例1
输入:
5 4 2 1 2 1 1 3 1 2 4 1 2 5 1 3 5 2 1
输出:
3 1
示例2
输入:
5 5 2 1 2 1 2 1 1 1 3 1 2 4 1 2 5 1 3 5 2 1
输出:
3 1
示例3
输入:
9 10 2 1 2 1 1 4 1 3 4 1 2 3 1 3 7 1 7 8 2 7 9 2 1 5 3 1 6 4 5 6 1 1 9 5 7
输出:
5 6
Java 解法, 执行用时: 125ms, 内存消耗: 17484K, 提交时间: 2021-09-03 23:35:40
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.Collection;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Queue;
import java.util.ArrayDeque;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
FredasPager solver = new FredasPager();
solver.solve(1, in, out);
out.close();
}
static class FredasPager {
int N = 12005;
int M = N * 4;
int[] h = new int[N];
int[] e = new int[M];
int[] ne = new int[M];
int[] w = new int[M];
int idx;
int[] dfn = new int[N];
int[] fa = new int[N];
int[] dist = new int[N];
int[] sum = new int[N];
int[] in = new int[N];
boolean[] vis = new boolean[N];
boolean[] broken = new boolean[M];
int[] lenCycle = new int[N];
int[] d = new int[N];
int T = 18;
int[][] f = new int[N][T];
int n;
int m;
int t;
int num;
int cnt;
public void solve(int testNumber, InputReader in, OutputWriter out) {
Arrays.fill(h, -1);
idx = 0;
n = in.nextInt();
m = in.nextInt();
t = in.nextInt();
for (int i = 1; i <= m; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
add(a, b, c);
add(b, a, c);
}
spfa();
dfs(1);
bfs();
for (int i = 0; i < t; i++) {
int a = in.nextInt();
int b = in.nextInt();
out.println(calc(a, b));
}
}
private int calc(int a, int b) {
if (d[a] < d[b]) {
int t = a;
a = b;
b = t;
}
int oa = a;
int ob = b;
for (int i = T - 1; i >= 0; i--) {
if (d[f[a][i]] >= d[b]) {
a = f[a][i];
}
}
if (a == b) {
return dist[oa] - dist[ob];
}
for (int i = T - 1; i >= 0; i--) {
if (f[a][i] != f[b][i]) {
a = f[a][i];
b = f[b][i];
}
}
if (in[a] == 0 || in[a] != in[b]) {
return dist[oa] + dist[ob] - 2 * dist[f[a][0]];
}
// 环上某个方向的距离
int l = Math.abs(sum[a] - sum[b]);
return dist[oa] - dist[a] + dist[ob] - dist[b] + Math.min(l, lenCycle[in[a]] - l);
}
void bfs() {
Queue<Integer> queue = new ArrayDeque<>();
queue.add(1);
d[1] = 1;
while (!queue.isEmpty()) {
Integer u = queue.poll();
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == 0 && !broken[i]) {
d[j] = d[u] + 1;
f[j][0] = u;
for (int k = 1; k < T; k++) {
f[j][k] = f[f[j][k - 1]][k - 1];
}
queue.add(j);
}
}
}
}
private void dfs(int u) {
dfn[u] = ++num;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (dfn[j] == 0) {
fa[j] = i;
dfs(j);
} else if ((i ^ 1) != fa[u] & dfn[j] >= dfn[u]) {
getCycle(u, j, i);
}
}
}
private void getCycle(int u, int j, int z) {
cnt++;
sum[j] = w[z];
broken[z] = broken[z ^ 1] = true;
while (j != u) {
in[j] = cnt;
int nextJ = e[fa[j] ^ 1];
sum[nextJ] = sum[j] + w[fa[j]];
broken[fa[j]] = broken[fa[j] ^ 1] = true;
add(u, j, dist[j] - dist[u]);
add(j, u, dist[j] - dist[u]);
j = nextJ;
}
in[u] = cnt;
lenCycle[cnt] = sum[u];
}
void spfa() {
Arrays.fill(dist, 0x3f3f3f3f);
dist[1] = 0;
Queue<Integer> queue = new ArrayDeque<>();
queue.add(1);
vis[1] = true;
while (!queue.isEmpty()) {
int t = queue.poll();
vis[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!vis[j]) {
queue.add(j);
vis[j] = true;
}
}
}
}
}
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private InputReader.SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new UnknownError();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new UnknownError();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new UnknownError();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void println(int i) {
writer.println(i);
}
}
}
C++ 解法, 执行用时: 61ms, 内存消耗: 2700K, 提交时间: 2022-02-25 19:45:36
#include<bits/stdc++.h>
using namespace std;
int x,y,t,n,m,q,to[40001],ntt[40001],last[40001],val[40001],num,nt[40001],nn[40001],nl[40001],nv[40001],cnt,dfn[20001],top,f[20001][15],g[20001][15],fa[20001],c1[20001],c2[20001],bl[20001],zx[20001],zz,d[20001],tt,vis[20001],sbll;
struct stack{int x,s;}st[20001];
void ad(int x,int y,int c){num++;to[num]=y;ntt[num]=last[x];last[x]=num;val[num]=c;}
void nad(int x,int y,int c){cnt++;nt[cnt]=y;nn[cnt]=nl[x];nl[x]=cnt;nv[cnt]=c;}
void dfs(int x){
dfn[x]=++tt;
for(int i=last[x];i;i=ntt[i]){
int v=to[i];
if(v!=fa[x]&&!dfn[v])fa[v]=x,top++,st[top].x=v,st[top].s=val[i],dfs(v);
else if(v!=fa[x]&&dfn[v]<dfn[x]){
zz++;
int p=top,tmp=val[i];
while(st[p].x!=v&&p)c1[st[p].x]=tmp,tmp+=st[p].s,p--;
tmp=st[p+1].s;
for(int i=p+1;i<=top;i++){zx[st[i].x]=v;bl[st[i].x]=zz;c2[st[i].x]=tmp;int jx=min(c1[st[i].x],c2[st[i].x]);nad(st[i].x,v,jx);nad(v,st[i].x,jx);tmp+=st[i+1].s;}
}
}
top--;
}
void cxlb(int x){
vis[x]=1;
for(int i=last[x];i;i=ntt[i]){
int v=to[i];
if(v-fa[x]&&!vis[v]){if((bl[x]-bl[v]||!bl[x]&&!bl[v])&&zx[v]-x&&zx[x]-v)nad(x,v,val[i]),nad(v,x,val[i]);cxlb(v);}
}
}
void find(int x){for(int i=nl[x];i;i=nn[i]){int v=nt[i];if(v-f[x][0])f[v][0]=x,g[v][0]=nv[i],d[v]=d[x]+1,find(v);}}
int lca(int x,int y){
int tmp=0;
if(d[x]>d[y]) swap(x,y);
for(int i=14;i>=0;i--)while(d[f[y][i]]>=d[x])tmp+=g[y][i],y=f[y][i];
if(x==y)return tmp;
for(int i=14;i>=0;i--)while(f[x][i]-f[y][i])tmp+=g[x][i]+g[y][i],x=f[x][i],y=f[y][i];
if(x-y&&bl[x]&&bl[x]==bl[y])tmp+=min(min(c1[x]+c2[y],c1[y]+c2[x]),min(abs(c2[x]-c2[y]),abs(c1[x]-c1[y])));
else tmp+=g[x][0]+g[y][0];
return tmp;
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<=m;i++)cin>>x>>y>>t,ad(x,y,t),ad(y,x,t);
dfs(1);
cxlb(1);
find(1);
d[0]=-1;
for(int j=1;j<=14;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1],g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];
for(int i=1;i<=q;i++)cin>>x>>y,cout<<lca(x,y)<<"\n";
return 0;
}