題意：
Given a sequence of streets (connecting given intersections) you are to write a program that determines the minimal cost tour that traverses every street at least once. The tour must begin and end at the same intersection.
給力條件：
There will be at most two intersections with odd degree解法：
分情況討論：
1、所有節點的度都為偶數，那么答案就是所有邊權和
2、存在兩個奇數度節點，那么答案是邊權和加上這兩個奇數度節點間的最短距離
發現現在越來越依賴STL了，有點小悲劇。。。
代碼：
1 # include <cstdio>
2 # include <vector>
3 # include <utility>
4 # include <functional>
5 # include <cstring>
6 using namespace std;
7 vector<pair<int,int> >g[26];
8 int main()
9 {
10 char str[1024];
11 while(scanf("%s",str)!=EOF)
12 {
13 int total=0;
14 for(int i=0;i<26;i++) g[i].clear();
15 while(true)
16 {
17 if(!strcmp(str,"deadend")) break;
18 g[str[0]-'a'].push_back(make_pair<int,int>(str[strlen(str)-1]-'a',strlen(str)));
19 g[str[strlen(str)-1]-'a'].push_back(make_pair<int,int>(str[0]-'a',strlen(str)));
20 total+=strlen(str);
21 scanf("%s",str);
22 }
23 vector<int> flag;
24 for(int i=0;i<26;i++)
25 {
26 if(g[i].size()%2==1)
27 flag.push_back(i);
28 }
29 if(flag.empty()) printf("%d\n",total);
30 else
31 {
32 int len[26];
33 bool used[26];
34 memset(len,-1,sizeof(len));
35 memset(used,false,sizeof(used));
36 len[flag[0]]=0;
37 while(true)
38 {
39 int pos=-1,minnum=0xfffffff;
40 for(int i=0;i<26;i++)
41 if(!used[i]&&len[i]!=-1&&len[i]<minnum)
42 minnum=len[i],pos=i;
43 if(pos==-1) break;
44 used[pos]=true;
45 for(int i=0;i<g[pos].size();i++)
46 if(!used[g[pos][i].first]&&(len[g[pos][i].first]==-1||len[g[pos][i].first]>len[pos]+g[pos][i].second))
47 len[g[pos][i].first]=len[pos]+g[pos][i].second;
48 }
49 printf("%d\n",total+len[flag[1]]);
50 }
51 }
52 return 0;
53 }
54