STEP5::Problem 0108 : 妹妹的遊戲

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0108
這題是基礎的樹的BFS(其實本來想寫DFS…..),跑完後在回朔路徑並加總。
寫的很難看……….

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
124
125
126
127
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <queue>
#define M 1000001
#define DR 1
using namespace std;
std::queue<int>noque,staque;
int n,m,q,viu[M],st[2*M][3],ste=-1,nno[M+1][2]={0};
int _walk(int sta,int en,int no,int now,int dr,int lon)//BFS
{
nno[sta][0]=no;
nno[sta][1]=lon;
if(sta==en)return 1;
//printf("AA:%d\n",sta);
if(now==dr){
noque.push(no);
staque.push(sta);
return -1;
}
int p=viu[sta],c=-1;
while(p!=-1){
if(st[p][0]==en){
nno[st[p][0]][0]=sta;
nno[st[p][0]][1]=st[p][1];
return 1;
}
else p=st[p][2];
}
p=viu[sta];
while(p!=-1){
if(st[p][0]!=no)c=_walk(st[p][0],en,sta,now+1,dr,st[p][1]);
if(c==-1)p=st[p][2];
else return 1;
}
return -1;
}
void _v(int a,int b,int c)//用來建立反向邊
{
if(viu[a]==-1){
viu[a]=ste+1;
st[++ste][0]=b;st[ste][1]=c;
}else{
int p=st[viu[a]][2];
if(p==-1) st[viu[a]][2]=ste+1;
else{
while(st[p][2]!=-1)p=st[p][2];
st[p][2]=ste+1;
}
st[++ste][0]=b;st[ste][1]=c;
}
}
int tt(int en)//路徑總和
{
int sum=0;
while(en!=-1){
sum+=nno[en][1];
en=nno[en][0];
//printf("sum:%d\n",sum);
}
return sum;
}
int main(){
for(int i=0;i<M;i++){viu[i]=-1;st[i][2]=-1;}
for(int i=M;i<2*M;i++){st[i][2]=-1;}
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
if(viu[a]==-1){
viu[a]=ste+1;
st[++ste][0]=b;st[ste][1]=c;
_v(b,a,c);
}else{
int p=st[viu[a]][2];
if(p==-1) st[viu[a]][2]=ste+1;
else{
while(st[p][2]!=-1)p=st[p][2];
st[p][2]=ste+1;
}
st[++ste][0]=b;st[ste][1]=c;
_v(b,a,c);
}
}
/*
for(int i=0;i<ste+1;i++)
printf("VVV %d\n",viu[i]);
for(int i=0;i<ste+1;i++)
printf("TTT %d %d %d\n",st[i][0],st[i][1],st[i][2]);
*/
int a,b,t,dd,c=-1,dr=DR;
scanf("%d %d",&a,&b);
t=_walk(a,b,c,1,dr,0);
while(t==-1){
dr+=DR;
dd=noque.size();
while(dd--){
a=staque.front();
c=noque.front();
//printf("A:%d\n",a);
staque.pop();
noque.pop();
t=_walk(a,b,c,dr-DR,dr,nno[a][1]);
if(t!=-1)break;
}
}
t=tt(b);
printf("%d\n",t*2);
/*
for(int i=0;i<ste+1;i++)
printf("nno:%d %d\n",nno[i][0],nno[i][1]);
*/
//system("pause");
return EXIT_SUCCESS;
}