這道題目和前面幾篇思路一樣，不用多說
問題是如果用spfa+隊列，肯定tle，換為堆棧就可以了，這題目也就是從頭不行，要從尾部開始，就是隊列和棧的區別了。
總感覺這題有問題。正向超時，反向484ms。。。。
代碼：
[cpp]
#include <stdio.h>
#define maxN 30005//最大邊條數
#define inf 0x7fffffff//最大距離
struct Edge
{
int v, w, next;
}edge[5 * maxN];//邊集
int dis[maxN];
bool vis[maxN];
int queue[30 * maxN];
int preEdge[maxN];//同一個頂點的前一條邊
int edgeNum,n,m;
void addEdge(int u, int v, int w)//添加一條邊
{
edge[edgeNum].v = v;
edge[edgeNum].w = w;
edge[edgeNum].next = preEdge[u];
preEdge[u] = edgeNum ++;
}
void spfa()//spaf算法
{
int head = 0, tail = 1, top = 0;
for (int i = 1; i <= n; ++ i)
{
dis[i] = inf;
}
//queue[head] = 1;
queue[top ++] = 1;
dis[1] = 0;
while (top/*head != tail*/)
{
//int u = queue[head];
int u = queue[-- top];
vis[u] = true;
for (int p = preEdge[u]; p != 0; p = edge[p].next)
{
int v = edge[p].v;
if (dis[v] > dis[u] + edge[p].w)
{
dis[v] = dis[u] + edge[p].w;
if (!vis[v])
{
vis[v] = true;
queue[top ++] = v;
//queue[tail] = v;
/*tail ++;
if (tail == maxN)
{
tail = 0;
}*/
}
}
}
vis[u] = false;
/*head ++;
if (head == maxN)
{
head = 0;
}*/
}
}
int main()
{
scanf("%d%d", &n, &m);
edgeNum = 1;
while (m --)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
}
spfa();
printf("%d\n", dis[n]);
return 0;
}
作者：zhang20072844
