HDU 2112 Today(Dijkstra+map)
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
题目链接
一道最短路径题，将站名编号后套用迪杰斯特拉，其中将站名编号可以用map进行操作。
无map的AC代码:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
struct connect {
int v;
int time;
};
string sta[150];
int dis[maxn],N,book = 0;
bool vis[maxn];
vector<connect> Adj[maxn];
void Dijkstra(int s) {
mem(dis, INF);
mem(vis, 0);
dis[s] = 0;
for (int i = 0;i < N;++i) {
int u = -1,min = INF;
for (int j = 1;j <= N;++j) {
if (vis[j] == 0 && dis[j] < min) {
u = j;
min = dis[j];
}
}
if (u == -1) {
return;
}
vis[u] = 1;
for (int j = 0;j < Adj[u].size();++j) {
int v = Adj[u][j].v;
if (vis[v] == 0 && dis[u] + Adj[u][j].time < dis[v]) {
dis[v] = dis[u] + Adj[u][j].time;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> N) {
if (N == -1) {
break;
}
book = 0;
int k = N;
string st,en;
cin >> st >> en;
while (k--) {
string a,b;
int num,num1 = -1,num2 = -1;
cin >> a >> b >> num;
for (int i = 1;i <= book;++i) {
if (a.compare(sta[i]) == 0) {
num1 = i;
}
if (b.compare(sta[i]) == 0) {
num2 = i;
}
}
if (num1 != -1 && num2 != -1) {
connect add;
add.v = num2;
add.time = num;
Adj[num1].push_back(add);
add.v = num1;
Adj[num2].push_back(add);
}
else if (num1 != -1 && num2 == -1) {
connect add;
add.v = ++book;
add.time = num;
Adj[num1].push_back(add);
add.v = num1;
Adj[book].push_back(add);
sta[book] = b;
}
else if (num1 == -1 && num2 != -1) {
connect add;
add.v = num2;
add.time = num;
Adj[++book].push_back(add);
add.v = book;
Adj[num2].push_back(add);
sta[book] = a;
}
else {
connect add;
add.v = book + 2;
add.time = num;
Adj[book + 1].push_back(add);
add.v = book + 1;
Adj[book + 2].push_back(add);
sta[book + 1] = a;
sta[book + 2] = b;
book += 2;
}
}
int start = -1,end = -1;
for (int i = 1;i <= book;++i) {
if (st.compare(sta[i]) == 0) {
start = i;
}
if (en.compare(sta[i]) == 0) {
end = i;
}
sta[i] = "";
}
Dijkstra(start);
if (dis[end] == INF || start == -1 || end == -1) {
cout << -1 << endl;
}
else {
cout << dis[end] << endl;
}
for (int i = 1;i <= N;++i) {
Adj[i].clear();
}
}
return 0;
}
map的AC代码:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const double eps = 1e-5;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
struct connect {
int v;
int time;
};
int n, num_station;
int dis[maxn];
bool res_flag;
bool vis[maxn];
map<string, int> cor;
vector<connect> Adj[maxn];
void Dijkstra(int s) {
mem(dis, INF);
mem(vis, 0);
dis[s] = 0;
for (int i = 0;i < n;++i) {
int u = -1,min = INF;
for (int j = 1;j <= n;++j) {
if (vis[j] == 0 && dis[j] < min) {
u = j;
min = dis[j];
}
}
if (u == -1) {
return;
}
vis[u] = 1;
for (int j = 0;j < Adj[u].size();++j) {
int v = Adj[u][j].v;
if (vis[v] == 0 && dis[u] + Adj[u][j].time < dis[v]) {
dis[v] = dis[u] + Adj[u][j].time;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> n) {
if (n == -1) {
break;
}
num_station = 0;
string start_road, end_road;
cin >> start_road >> end_road;
cor[start_road] = ++num_station;
cor[end_road] = ++num_station;
for (int i = 1; i <= n; ++i) {
string Input1, Input2;
int distance;
cin >> Input1 >> Input2 >> distance;
if (!cor[Input1]) {
cor[Input1] = ++num_station;
}
if (!cor[Input2]) {
cor[Input2] = ++num_station;
}
connect add;
add.v = cor[Input2];
add.time = distance;
Adj[cor[Input1]].push_back(add);
add.v = cor[Input1];
Adj[cor[Input2]].push_back(add);
}
Dijkstra(cor[start_road]);
if (start_road == end_road) {
cout << 0 << endl;
}
else if (dis[cor[end_road]] == INF) {
cout << -1 << endl;
}
else {
cout << dis[cor[end_road]] << endl;
}
for (int i = 0; i <= n; ++i) {
Adj[i].clear();
}
cor.clear();
}
return 0;
}
查看16道真题和解析
