題意：
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、所有節(jié)點的度都為偶數(shù)，那么答案就是所有邊權(quán)和
2、存在兩個奇數(shù)度節(jié)點，那么答案是邊權(quán)和加上這兩個奇數(shù)度節(jié)點間的最短距離
發(fā)現(xiàn)現(xiàn)在越來越依賴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