题意：
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