Choose the best route HDU 各种优化加错误解析

本文主要是介绍Choose the best route HDU 各种优化加错误解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Choose the best route

题目链接

题目不难，就是如果看到题目的时候就能想到反向建图的话。那该题就相当于一道水题。但是这道题可以延伸出很多的内容，所以个人感觉有必要写一篇博客纪念一下。

根据题目的要求知道，如果按常规的思路的话，数据太大会超时。所以我们想到了因为终点就一个，所以我们反向建图，把终点当起点。然后本题是有重边的，一开始我是用邻接表写的所以被我侥幸AC了。但之后我用矩阵开始的时候也是一直错，后来看了别人的才知道，要去除重边。因而该道题如果是用矩阵的话，就不能用普通的BellmanFord了，在仔细思考一下为什么？？？因为BellmanFord的算法是用m条边进行松弛的，但是当有重边的时候，实际上边是少于m的，所以会造成错误。这里大家以后做题要多注意，特别是最短路的重边问题。

还有该题的输入数据是恶心的多，开始的时候TEL。后来用了外挂，就轻松上版了

Spfa版

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;const int EN = 2e4 + 10;
const int VN = 1e3 + 10;
const int INF = 0x7fffffff >> 1;
struct Edge{int v,nxt,w;}E[EN];
int n,size,d[VN],head[VN];inline int ReadInt()
{char c = getchar();while(!isdigit(c)) c = getchar();int x = 0;while(isdigit(c)){x = x *10 + c - '0';c = getchar();}return x;
}
void Clear()
{size = 0;memset(head,-1,sizeof(head));
}
void AddEdge(int u,int v,int w)
{E[size].v = v,E[size].w = w;E[size].nxt = head[u];head[u] = size++;
}void Spfa(int start)
{bool inq[VN];queue<int> q;for(int i = 0;i <= n;i++){inq[i] = 0;d[i] = i == start ? 0 : INF;}q.push(start);while(!q.empty()){int u = q.front();q.pop();inq[u] = 0;for(int e = head[u];e != -1;e = E[e].nxt)if(d[u] + E[e].w < d[E[e].v]){d[E[e].v] = d[u] + E[e].w;if(!inq[E[e].v]){inq[E[e].v] = 1;q.push(E[e].v);}}}
}
int main()
{int m,gold;while(~scanf("%d%d%d",&n,&m,&gold)){Clear();for(int i = 0;i != m;i++){int u,v,w;u = ReadInt();v = ReadInt();w = ReadInt();AddEdge(v,u,w);}Spfa(gold);m = ReadInt();int s,ans = INF;for(int i = 0;i != m;i++){s = ReadInt();if(d[s] < ans) ans = d[s];}if(ans == INF)printf("-1\n");elseprintf("%d\n",ans);}return 0;
}

Dijkstra STL版

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;typedef pair<int,int> pii;
const int EN = 2e4 + 10;
const int VN = 1e3 + 10;
const int INF = 0x7fffffff >> 1;
struct Edge{int v,nxt,w;}E[EN];
int n,size,d[VN],head[VN];inline int ReadInt()
{char c = getchar();while(!isdigit(c)) c = getchar();int x = 0;while(isdigit(c)){x = x *10 + c - '0';c = getchar();}return x;
}
void Clear()
{size = 0;memset(head,-1,sizeof(head));
}
void AddEdge(int u,int v,int w)
{E[size].v = v,E[size].w = w;E[size].nxt = head[u];head[u] = size++;
}void Dijkstra(int start)
{priority_queue<pii,vector<pii>,greater<pii> > q;for(int i = 0;i <= n;i++) d[i] = i == start ? 0 : INF;q.push(make_pair(d[start],start));while(!q.empty()){pii u = q.top();q.pop();int index = u.second;if(d[index] != u.first) continue;for(int e = head[index];e != -1;e = E[e].nxt)if(d[index] + E[e].w < d[E[e].v]){d[E[e].v] = d[index] + E[e].w;q.push(make_pair(d[E[e].v],E[e].v));}}
}
int main()
{int m,gold;while(~scanf("%d%d%d",&n,&m,&gold)){Clear();for(int i = 0;i != m;i++){int u,v,w;u = ReadInt();v = ReadInt();w = ReadInt();AddEdge(v,u,w);}Dijkstra(gold);m = ReadInt();int s,ans = INF;for(int i = 0;i != m;i++){s = ReadInt();if(d[s] < ans) ans = d[s];}if(ans == INF)printf("-1\n");elseprintf("%d\n",ans);}return 0;
}

普通的Dijkstra版

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int VN = 1e3 + 10;
const int INF = 0x7fffffff >> 1;
int n,m,d[VN],w[VN][VN];inline int ReadInt()
{char c = getchar();while(!isdigit(c)) c = getchar();int x = 0;while(isdigit(c)){x = x *10 + c - '0';c = getchar();}return x;
}
void Dijkstra(int gold)
{bool vist[VN];memset(vist,0,sizeof(vist));for(int i = 0;i <= n;i++)d[i] = i == gold ? 0 : INF;for(int i = 1;i < n;i++){int x,m = INF;for(int y = 1;y <= n;y++)if(!vist[y]&&d[y] < m)m = d[x = y];vist[x] = 1;if(d[x] == INF) break;for(int y = 1;y <= n;y++)if(d[y] > d[x] + w[x][y])d[y] = d[x] + w[x][y];}
}
int main()
{int gold;while(~scanf("%d%d%d",&n,&m,&gold)){for(int i = 0;i <= n;i++)for(int j = 0;j <= n;j++)w[i][j] = INF;for(int i = 0;i != m;i++){int u,v;u = ReadInt();v = ReadInt();int tmp = ReadInt();if(tmp < w[v][u]) //判断是否有重边w[v][u] = tmp;}Dijkstra(gold);int btot,s,ans = INF;btot = ReadInt();for(int i = 0;i != btot;i++){s = ReadInt();if(gold != s&&d[s] < ans) ans = d[s];}if(ans == INF)printf("-1\n");elseprintf("%d\n",ans);}return 0;
}

这篇关于Choose the best route HDU 各种优化加错误解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！