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