題意：成語接龍的游戲，一個(gè)中文字是四個(gè)字符組成，所以只要一個(gè)字符串后四個(gè)字符與另一個(gè)字符串的頭四個(gè)字符能匹配，那么就能接上，求出從第一個(gè)到最后一個(gè)的最短時(shí)間。

不知道是建圖的問題還是什么，一直WA。。。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 1005; const int inf = 0x7fffff; struct Node {int t;char first[5],last[5]; }word[maxn]; int n,map[maxn][maxn],dis[maxn]; char str[maxn]; bool vis[maxn];void build() {for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){if(strcmp(word[i].last,word[j].first) == 0)map[i][j] = word[i].t;else map[i][j] = inf;} }void Dijkstra(int s) {int k = s,MIN;memset(vis,false,sizeof(vis));for(int i = 1; i <= n; i++)if(i != s)dis[i] = map[s][i];vis[k] = true;for(int i = 1; i < n; i++){MIN = inf;for(int j = 1; j <= n; j++){if(vis[j] == true) continue;if(MIN > dis[j]){MIN = dis[j];k = j;}}vis[k] = true;for(int j = 1; j <= n; j++)if(vis[j] == false && dis[j] > dis[k] + map[k][j])dis[j] = dis[k] + map[k][j];} }int main() {while(scanf("%d",&n),n){for(int i = 1; i <= n; i++){scanf("%d %s",&word[i].t,str);for(int j = 0; j < 4; j++){word[i].first[j] = str[j];word[i].last[j] = str[j+12];}}build();Dijkstra(1);printf("%d\n",dis[n] == inf ? -1 : dis[n]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1546（最短路）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。