// UVa 117 - The Postal Worker Rings Once #include <iostream> #include <string> #include <string.h> using namespace std; int lnk['z' + 1]['z' + 1], oo; int dijkstra(int start, int end) { bool taken['z' + 1]; int dist['z' + 1]; memset(taken, false, sizeof(taken)); memset(dist, 127, sizeof(dist)); dist[start] = 0; int next = start; while (next != end && next != -1) { taken[next] = true; for (char c = 'a'; c <= 'z'; c++) if (dist[c] > dist[next] + lnk[next][c]) dist[c] = dist[next] + lnk[next][c]; next = -1; for (char c = 'a'; c <= 'z'; c++) { if (!taken[c] && (next == -1 || dist[c] < dist[next])) next = c; } } return dist[end]; } int main() { string st; while (getline(cin, st)) { int sol = 0; memset(lnk, 127, sizeof(lnk)); oo = lnk[0][0]; int degree['z' + 1]; memset(degree, 0, sizeof(degree)); while (st != "deadend") { char a = st[0], b = st[st.length() - 1]; lnk[a][b] = lnk[b][a] = st.length(); degree[a]++; degree[b]++; sol += st.length(); getline(cin, st); } int start, end; bool odd = false; for (int c = 'a'; c <= 'z'; c++) { if (degree[c] & 1) { start = end; end = c; odd = true; } } if (odd) sol += dijkstra(start, end); cout << sol << endl; } return 0; }
Saturday, June 6, 2015
UVa 117 - The Postal Worker Rings Once
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment