路径归并,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
#include <stdio.h>
const int LEN = 40005;
int p[LEN];
void make ( int n ) { for ( int i=0; i<n; i++ ) { p[i] = -1; } }
int find ( int a ) {
if ( p[a] < 0 ) { return a; } int r = find ( p[a] ); p[a] = r;
return r; }
void un ( int a, int b ) {
int ra = find ( a ); int rb = find ( b );
p[rb] = ra; }
struct { int c;/**//*记录结点的入度*/ int last;/**//*记录最后一个节点的地址*/ int next; }tab[LEN];/**//*邻接链表头,记录最后一个节点的地址*/ typedef struct { int num; int dis;//记录边的长度 int addr;//记录位置 int next; }type; type node[LEN*2]; int next1; /**//*下一个可以使用的位置*/
void initm ( int n ) {
next1 = 0; for ( int i=0; i<n; i++ ) { tab[i].c = 0; tab[i].last = -1; tab[i].next = -1; } }
void adde ( int b, int e, int dis )/**//*增加一条边*/ {
node[next1].num = e; node[next1].next = -1; node[next1].dis = dis; if ( tab[b].next >= 0 ) { node[ tab[b].last ].next = next1; } else { tab[b].next = next1; } tab[b].last = next1; tab[e].c ++; next1 ++; }
struct { int next; int last; }que[LEN]; type q[LEN*2]; int next2;
void initq ( int n ) {
next2 = 0; for ( int i=0; i<n; i++ ) { que[i].last = -1; que[i].next = -1; } }
void addq ( int b, int e, int addr )/**//*增加一个问题*/ {
q[next2].num = e; q[next2].next = -1; q[next2].addr = addr; if ( que[b].next >= 0 ) { q[ que[b].last ].next = next2; } else { que[b].next = next2; } que[b].last = next2; next2 ++; }
int color[LEN];//并且记录从根结点到当前结点走的距离
int di[LEN];//记录根结点到当前结点的距离
int used[LEN];//距离是否访问过
int qustion[LEN];//记录问题的答案
void initc ( int n ) {
for ( int i=0; i<n; i++ ) { color[i] = 0; di[i] = 0; used[i] = 0; } used[0] = 1; }
void lca ( int p, int dis ) {
di[p] = dis; for ( int i=tab[p].next; i!=-1; i=node[i].next ) { if ( ! used[ node[i].num ] ) { used[ node[i].num ] = 1; lca ( node[i].num, dis + node[i].dis ); un ( p, node[i].num ); } }
for ( i=que[p].next; i!=-1; i=q[i].next ) { if ( color[ q[i].num ] ) { qustion[ q[i].addr ] = di[p] + di[ q[i].num ] - 2 * di[ find ( q[i].num ) ]; } } color[p] = 1; }
int main () {
int n, m; int a, b, l; char in[5]; int k; int f1, f2; int i;
while ( scanf ( "%d%d", &n, &m ) != EOF ) { initm ( n ); for ( i=0; i<m; i++ ) { scanf ( "%d%d%d%s", &a, &b, &l, in ); adde ( a-1, b-1, l ); adde ( b-1, a-1, l ); }
scanf ( "%d", &k ); initq ( n ); for ( i=0; i<k; i++ ) { scanf ( "%d%d", &f1, &f2 ); addq ( f1-1, f2-1, i ); addq ( f2-1, f1-1, i ); }
make ( n ); initc ( n ); lca ( 0, 0 );
for ( i=0; i<k; i++ ) { printf ( "%d\n", qustion[i] ); } }
return 0; }
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
30 | 31 | 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 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|