这个题实在是坑,天坑!!!
题目意思是给你一些成语,然后这些成语都是四个字组成, 如果两个成语能连接那么第一个的最后一个字要和第二个的第一个字相同。这里的成语用16个字符来表示,也就是说我们只要取前四个和后四个字符就可以了。然后建图,由于这里数据小,用邻接矩阵就OK。但是,,,字符这里要注意了,为了方便我们后面比较,第5个字符要设置为'\0',不然不好比较啊喂,开始还傻傻地写了一个字符比较函数。然后就是,这题最好用C++编译过,G++坑爹啊坑,一个变量位置引发了血案,我把自己开始TLE的代码提交后比看题解ac的代码时间还要短。happy_code的代码还因为字符数组设为50不能过,设为100能过,可我明明只要18就ac了啊,他把别人代码改改,测试案例都过不了竟然能ac?ORZ,,,
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1546
代码:
Memory: 1796 KB | Time: 171 MS | |
Language: C++ | Result: Accepted |
#include <iostream> #include <cstdio> #include <cstring> #include <memory.h> using namespace std; #define MAX 10010 #define MAXV 1000000000 struct Word{ char s[5]; char e[5]; int v; }word[MAX]; int dis[MAX], flag[MAX], go[MAX], n, v; char str[18]; void Dij(){ dis[1] = 0; go[1] = 1; for(int i=1;i<=n;i++){ int cur = 1; int nowv = MAXV; for(int j=1;j<=n;j++){ if(!go[j]&&dis[j]<nowv){ cur=j; nowv=dis[cur]; } } go[cur] = 1; for(int j=1;j<=n;j++){ if(cur==j)continue; if(!strcmp(word[cur].e, word[j].s) && !go[j]){ if(dis[cur]+word[cur].v<dis[j]) dis[j]=dis[cur]+word[cur].v; } } } } int main() { while(~scanf("%d", &n) && n){ memset(go, 0, sizeof(go)); for(int i=1;i<=n;i++)dis[i]=MAXV; for(int i=1;i<=n;i++){ scanf("%d %s", &v, &str); word[i].v = v; for(int j=0;j<4;j++)word[i].s[j]=str[j]; int tpos = 0; int pos = strlen(str)-4; for(int k=pos;k<pos+4;k++)word[i].e[tpos++]=str[k]; dis[i] = 10e9; word[i].s[4]=word[i].e[4]='\0'; } Dij(); if(!go[n])printf("-1\n"); else printf("%d\n", dis[n]); } return 0; }