题目链接：
2027
题意：
暑假快到了，Samball 想取旅行，现在可以制定一个计划了。选定旅行目的地后，接下来就是选择旅行路线了。由于他并没有多少钱，所以他想找一条最省钱的路线。Samball 得知旅游公司在暑假会推出一个折扣方案：选定一条线路后，在这条线路上连接两个城市间机票费用最贵的费用将被免去，这可是个好消息。给定出发地和目的地，以及所有机票的费用，请计算最小的费用。假定Samball 选定的航线没有回路，，并且出发地总是可以到达目的地的。
解题思路：
先通过floyed求一次整张图的最短路，更新得所有通路；
再结合floyed思想和dp思想：dp[i][j][1]=min(dp[i][j][1],min((dp[i][k][0]+dp[k][j][1]),(dp[i][k][1]+dp[k][j][0])));
其中dp[i][j][0] 表示从i到j的最短路径 dp[i][j][1]表示i到j减去一条最长边的最短路径。
注意初始化出现过的边dp[i][j][1]=0.
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxx 0x3f3f3f3fusing namespace std;int dp[105][105][2];char str[205][20];int s;int min(int a,int b){return a>b?b:a;}int floyed(){int i,j,k;for(k=0;k<s;k++)for(i=0;i<s;i++)for(j=0;j<s;j++)dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+dp[k][j][0]);for(k=0;k<s;k++)for(i=0;i<s;i++)for(j=0;j<s;j++)dp[i][j][1]=min(dp[i][j][1],min((dp[i][k][0]+dp[k][j][1]),(dp[i][k][1]+dp[k][j][0])));return dp[0][1][1];}int main(){int a,b,c,n,i,j;char str1[20],str2[20];while(~scanf("%s%s",str1,str2)){s=0;memset(dp,maxx,sizeof(dp));for(i=0; i<strlen(str1); i++)str[s][i]=str1[i];str[s++][i]='\0';for(i=0; i<strlen(str2); i++)str[s][i]=str2[i];str[s++][i]='\0';scanf("%d",&n);while(n–){scanf("%s%s%d",str1,str2,&c);a=b=-1;for(i=0; i<s; i++){if(strcmp(str1,str[i])==0)a=i;if(strcmp(str2,str[i])==0)b=i;}if(a==-1){for(i=0; i<strlen(str1); i++)str[s][i]=str1[i];str[s++][i]='\0';a=s-1;}if(b==-1){for(i=0; i<strlen(str2); i++)str[s][i]=str2[i];str[s++][i]='\0';b=s-1;}dp[a][b][1]=0;dp[a][b][0]=c;}for(i=0; i<s; i++)dp[i][i][0]=dp[i][i][1]=0;cout<<floyed()<<endl;}return 0;}
始终调整好自己观风景的心态，
