Idiomatic Phrases Game(图论最短路)
Idiomatic Phrases Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3504 Accepted Submission(s): 1182
Problem Description
Tom is playing a game called Idiomatic Phrases Game. An idiom consists of several Chinese characters and has a certain meaning. This game will give Tom two idioms. He should build a list of idioms and the list starts and ends with the two given idioms. For every two adjacent idioms, the last Chinese character of the former idiom should be the same as the first character of the latter one. For each time, Tom has a dictionary that he must pick idioms from and each idiom in the dictionary has a value indicates how long Tom will take to find the next proper idiom in the final list. Now you are asked to write a program to compute the shortest time Tom will take by giving you the idiom dictionary.
Input
The input consists of several test cases. Each test case contains an idiom dictionary. The dictionary is started by an integer N (0 < N < 1000) in one line. The following is N lines. Each line contains an integer T (the time Tom will take to work out) and an idiom. One idiom consists of several Chinese characters (at least 3) and one Chinese character consists of four hex digit (i.e., 0 to 9 and A to F). Note that the first and last idioms in the dictionary are the source and target idioms in the game. The input ends up with a case that N = 0. Do not process this case.
Output
One line for each case. Output an integer indicating the shortest time Tome will take. If the list can not be built, please output -1.
Sample Input
Sample Output
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF = 0x6f6f6f6f;
int n;
struct Idiom
{
int spend;
char str[];//好坑,50反正是错的,100才对,成语原来还有这么多字
}idiom[]; int spe[][]; int vis[],dis[];
void Dijkstra()
{
int i,j,mmm,m;
memset(vis,,sizeof(vis));
memset(dis,0x6f,sizeof(dis));
dis[] = ;
for(i = ; i<=n; i++)
{
mmm = INF;
for(j = ; j<=n; j++)
{
if(dis[j]<mmm &&!vis[j])
{
m = j;
mmm = dis[j];
}
}
vis[m] = ;
for(j = ; j<=n; j++)
{
if(dis[m]+spe[m][j]<dis[j]&&!vis[j])
dis[j] = dis[m]+spe[m][j];
}
}
} int main()
{
int i,j,len;
while(scanf("%d",&n)&&n)
{
for(i = ; i<=n; i++)
scanf("%d%s",&idiom[i].spend,idiom[i].str);
for(i = ; i<=n; i++)
{
len = strlen(idiom[i].str);
for(j = ; j<=n; j++)
{
if(idiom[i].str[len-]==idiom[j].str[]&&
idiom[i].str[len-]==idiom[j].str[]&&
idiom[i].str[len-]==idiom[j].str[]&&
idiom[i].str[len-]==idiom[j].str[])
spe[i][j]=idiom[i].spend;
else
spe[i][j]=INF;
}
}
Dijkstra();
if (dis[n]!=INF)
printf("%d\n",dis[n]);
else
printf("-1\n");
}
return ;
}
最新文章
- ACM/ICPC2016 青岛区域赛
- 使用SQL Server维护计划实现数据库定时自动备份
- Linux下用freetds连接mssql中文乱码的问题【参考2】
- Python全栈开发-web框架之django
- 大学生程序猿IT情书“2014爱的告白挑战赛”获奖名单及优秀情书展示系列之 - 【IT术语】情书+【搞笑另类】情书
- (10)Xamarin.Android - 储存数据于Windows Azure
- hadoop搭建杂记:Linux下hadoop的安装配置
- js与DOM初步:访问html元素
- 在VC/MFC中嵌入Google地图——图文并茂
- Arraylist、Linkedlist遍历方式性能分析
- windows下使用命令行给通过genymotion创建的虚拟机配制IP地址
- bzoj 1758: [Wc2010]重建计划
- Linux安装配置Mariadb
- JMeter&#160;后置处理器之正则表达式提取器详解
- valueof toString
- 虚拟化技术之KVM
- Python基础之Python分类
- (转)实现一个cache装饰器,实现过期可清除功能
- HLS:OpenCV和RTL代码转换关系
- javascript 排序
热门文章
- 由jtable浅谈vector<;vector<;Object>;>;的用法(转自a718515028的专栏)
- ubuntu16.04 ssh服无法远程连接解决办法
- vim常用操作之复制剪切粘贴,注释取消注释,多行缩进等
- 弄清java中的字节与字符
- linux下eclipse闪退和重装jdk的方法
- linux的chown命令
- selenium实现失败重运行
- kibana显示elasticsearch集群中flume到入的日志
- 解决dubbo问题:forbid consumer(1)
- 最新iOS发布App Store详细图文教程~