本文主要是介绍HDU - 3499 - Flight （分层图最短路 + map），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3499
题意：n个城市m条单向边！！！然后给你这M条单向边。最后输入起点终点，你有一次机会可以使某条边的花费减半，问起点到的最短路为多少？如果没有路可以到达输出“-1”。
思路：用map映射相应的地点，然后套分层图最短路模板。注意开long long。
直接建图AC代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
int n, m, s, t;
ll d[maxn]; int vis[maxn];
vector<pii>E[maxn];
void init()
{for(int i = 0; i <= n*2; i++) E[i].clear();memset(d,127,sizeof(d));memset(vis,0,sizeof(vis));
}
void Dijkstra()
{d[s] = 0;priority_queue<pii> Q;Q.push({-d[s],s});while(!Q.empty()){int now = Q.top().second;Q.pop(); if(vis[now]) continue;vis[now] = 1;for(int j = 0; j < E[now].size(); j++){int v = E[now][j].first;if(!vis[v] && d[v] > d[now]+E[now][j].second){d[v] = d[now]+E[now][j].second;Q.push({-d[v],v});}}}
}
int main()
{while(~scanf("%d%d",&n,&m)){init();string a, b; int x, p = 0;map <string, int> mp;while(m--){cin >> a >> b >> x;if(!mp.count(a)) mp[a] = p++;if(!mp.count(b)) mp[b] = p++;E[mp[a]].push_back({mp[b],x});E[mp[a]+n].push_back({mp[b]+n,x});E[mp[a]].push_back({mp[b]+n,x/2});}cin >> a >> b;if(!mp.count(a) || !mp.count(b)){puts("-1"); continue;}s = mp[a], t = mp[b];Dijkstra(); printf("%lld\n", d[t+n]);}return 0;
}
多开一维AC代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
#define ll long long
#define inf 9187201950435737471
#define pii pair<ll, ll>
int n, m, s, t, k;
ll d[maxn][5]; int vis[maxn][5];
vector<pii>E[maxn];
void init()
{for(int i = 0; i <= n; i++) E[i].clear();memset(d,127,sizeof(d));memset(vis,0,sizeof(vis));
}
void Dijkstra()
{d[s][0] = 0;priority_queue<pii> Q;Q.push({0,s});while(!Q.empty()){int now = Q.top().second; Q.pop();int c = now / n; now %= n;if(vis[now][c]) continue;vis[now][c] = 1;for(int j = 0; j < E[now].size(); j++){int v = E[now][j].first;if(!vis[v][c] && d[v][c] > d[now][c]+E[now][j].second){d[v][c] = d[now][c] + E[now][j].second;Q.push({-d[v][c],v + c * n});}}if(c < k){for(int j = 0; j < E[now].size(); j++){int v = E[now][j].first;if(!vis[v][c+1] && d[v][c+1] > d[now][c]+E[now][j].second/2){d[v][c+1] = d[now][c] + E[now][j].second/2;Q.push({-d[v][c+1],v + (c+1) * n});}}}}
}
int main()
{while(~scanf("%d%d",&n,&m)){init();string a, b; ll x; int p = 0;map <string, int> mp;while(m--){cin >> a >> b >> x;if(!mp.count(a)) mp[a] = p++;if(!mp.count(b)) mp[b] = p++;E[mp[a]].push_back({mp[b],x});}cin >> a >> b; k = 1;if(!mp.count(a) || !mp.count(b)){puts("-1"); continue;}s = mp[a], t = mp[b];Dijkstra(); printf("%lld\n", d[t][1]);}return 0;
}
这篇关于HDU - 3499 - Flight （分层图最短路 + map）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
