-
Notifications
You must be signed in to change notification settings - Fork 0
/
uva00117.cpp
executable file
·91 lines (81 loc) · 2.27 KB
/
uva00117.cpp
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
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15);
#define UNVISITED -1
#define POS_INF 1 << 28
#define NEG_INF -1 << 28
using namespace std;
typedef long long int64;
typedef pair<int, int> ii;
int total;
map<char, int> char2int;
vector< vector< ii > > AdjList;
void read_input(string &line){
char start = line[0], end = line.back();
if(char2int.count(start) == 0){
char2int[start] = AdjList.size();
AdjList.push_back(vector< ii > (0));
}
if(char2int.count(end) == 0){
char2int[end] = AdjList.size();
AdjList.push_back(vector< ii > (0));
}
int u = char2int[start], v = char2int[end];
AdjList[u].push_back(ii(v, line.size()));
AdjList[v].push_back(ii(u, line.size()));
total += line.size();
}
int dijkstra(int root, int target){
int n = AdjList.size();
vector<int> dist(n, POS_INF);
priority_queue< ii, vector< ii >, greater<ii> > pq;
pq.push(ii(0, root));
while(pq.size()){
int u, d1;
tie(d1, u) = pq.top();
pq.pop();
if(d1 > dist[u]) continue;
for(int i = 0; i < AdjList[u].size(); ++i){
int v, d2;
tie(v, d2) = AdjList[u][i];
if(d1 + d2 < dist[v]){
dist[v] = d1 + d2;
pq.push(ii(dist[v], v));
}
}
}
return dist[target];
}
int process(){
// find if there are odd nodes
// if there is none, then the whole tour is a euler tour
// we can just return the total length of all streets
int odd1 = -1, odd2 = -1;
for(int i = 0; i < AdjList.size(); ++i){
if(AdjList[i].size() % 2){
if(odd1 != -1) odd2 = i;
else odd1 = i;
}
}
// if there are, we should compute the shortest distance between them
// and add them to the euler tour since we need to finish at the starting node
if(odd1 != -1) total += dijkstra(odd1, odd2);
return total;
}
void init(){
total = 0;
AdjList.clear();
char2int.clear();
}
int main(){ _
string line;
init();
while(cin >> line){
if(line == "deadend"){
cout << process() << endl;
init();
continue;
}
read_input(line);
}
return 0;
}