HDU Today
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13396 Accepted Submission(s): 3144
Problem Description 經過錦囊相助,海東集團終于度過了危機,從此,HDU的發展就一直順風順水,到了2050年,集團已經相當規模了,據說進入了錢江肉絲經濟開發區500強。這時候,XHD夫婦也退居了二線,并在風景秀美的諸暨市浬浦鎮陶姚村買了個房子,開始安度晚年了。
這樣住了一段時間,徐總對當地的交通還是不太了解。有時很郁悶,想去一個地方又不知道應該乘什麼公共汽車,在什麼地方轉車,在什麼地方下車(其實徐總自己有車,卻一定要與民同樂,這就是徐總的性格)。
徐總經常會問蹩腳的英文問路:“Can you help me?”。看着他那迷茫而又無助的眼神,熱心的你能幫幫他嗎?
請幫助他用最短的時間到達目的地(假設每一路公共汽車都隻在起點站和終點站停,而且随時都會開)。
Input 輸入資料有多組,每組的第一行是公共汽車的總數N(0<=N<=10000);
第二行有徐總的所在地start,他的目的地end;
接着有n行,每行有站名s,站名e,以及從s到e的時間整數t(0<t<100)(每個地名是一個長度不超過30的字元串)。
note:一組資料中地名數不會超過150個。
如果N==-1,表示輸入結束。 Output 如果徐總能到達目的地,輸出最短的時間;否則,輸出“-1”。 Sample Input 6 xiasha westlake xiasha station 60 xiasha ShoppingCenterofHangZhou 30 station westlake 20 ShoppingCenterofHangZhou supermarket 10 xiasha supermarket 50 supermarket westlake 10 -1 Sample Output 50 Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake 雖然偶爾會迷路,但是因為有了你的幫助 **和**從此還是過上了幸福的生活。 ――全劇終―― 分析:題目意思很簡單,求最短路,要注意的是頂點名稱都換成了字元串,要重新标記,還有就是起點和終點重合的情況需要考慮。 問題:用string來存儲字元串應該是很友善的,但是不知道為什麼全部用string來表示,用cin輸入無限逾時啊。後面改為字元數組了然後用scanf居然就過了,太坑爹。 代碼如下:
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define maxn 155
#define INF 10000000
int w[maxn][maxn];
struct node
{
int u, key;
friend bool operator<(node a, node b)
{
return a.key > b.key;
}
};
bool visited[maxn];
node d[maxn];
priority_queue<node> q;
char stn[maxn][35];
int sno;
void Dijkstra(int s)
{
for(int i = 0; i < sno; i++)
{
d[i].u = i;
d[i].key = INF;
visited[i] = false;
}
d[s].key = 0;
q.push(d[s]);
while(!q.empty())
{
node nd = q.top();
q.pop();
int st = nd.u;
if(visited[st] == true)
continue;
visited[st] = true;
for(int j = 0; j < sno; j++)
{
if(j!=st && !visited[j] && w[st][j]+d[st].key < d[j].key)
{
d[j].key = w[st][j]+d[st].key;
q.push(d[j]);
}
}
}
}
int Find(char s[])
{
for(int i = 0; i < sno; i++)
if(strcmp(stn[i], s)==0)
return i;
return -1;
}
int main()
{
int n, c, x, y;
char st[35], ed[35], a[35], b[35];
while(scanf("%d", &n), n!=-1)
{
for(int i = 0; i <= maxn; i++)
for(int j = i; j <= maxn; j++)
w[i][j] = w[j][i] = INF;
scanf("%s%s", st, ed);
strcpy(stn[0], st);
strcpy(stn[1], ed);
sno = 2;
while(n--)
{
scanf("%s %s %d", a, b, &c);
x = Find(a);
if(x == -1)
{
x = sno;
//stn[sno++] = a;
strcpy(stn[sno++], a);
}
y = Find(b);
if(y == -1)
{
y = sno;
strcpy(stn[sno++], b);
}
if(w[x][y] > c)
w[x][y] = w[y][x] = c;
}
if(strcmp(st, ed)==0)
{
printf("0\n");
continue;
}
Dijkstra(0);
if(d[1].key < INF)
printf("%d\n", d[1].key);
else
printf("-1\n");
}
return 0;
}