学步园

学了最短路，特意挑的，，最简单的。。难度1的。。题目

一开始写的邻接矩阵的dijkstra+Heap

妥妥的超时5个点

然后咱把邻接矩阵费好大劲改成邻接表。。。

妥妥的超时6个点。。。

于是乎我想起了传说中的SPFA算法。。。

用邻接矩阵弄了一下，呀嘿！只超时4个点了。。

我又费好大劲改成邻接表，，还是超时4个点。。。。

于是我放弃了，，，先刷刷生成树哈。。。看到一道题poj的题。。

下边有提示: Huge input,scanf is recommoned;

我看到了scanf。。。。。

然后把原来那道题的cin全改成scanf，妥妥的过了。。。。。。。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
#define INT_MAX 2146473647
#define MAX 1001
typedef struct node
{
	int dis;
	int end;
	int las;
}node;
node map[MAX*MAX];
int n,top,last[MAX];
queue<int> Q;
int dist[MAX],road[MAX];
bool vis[MAX];
void add(int i,int j,int p)
{
	map[++top].dis = p;
	map[top].end = j;
	map[top].las = last[i];
	last[i] = top;
}
void updata(int j)
{
	int wh = last[j];
	while(wh)
	{
		int k = map[wh].end;
		if ( dist[k] > dist[j] + map[wh].dis )
		{
			dist[k] = dist[j] + map[wh].dis;
			road[k] = j;
			if ( vis[k] == false )
			{
				Q.push(k);
				vis[k] = true;
			}
		}
		wh = map[wh].las;
	}
}
void spfa()
{
	for (int i = 1; i <= n; i++)
	{
		dist[i] = INT_MAX;
	}
	dist[1] = 0;
	updata(1);
	while(!Q.empty())
	{
		int x = Q.front();
		Q.pop();
		updata(x);
		vis[x] = false;
	}
}
void end()
{
	int ans[n+1],top = 0;
	int wh = n;
	while(wh)
	{
		ans[++top] = wh;
		wh = road[wh];
	}
	for (int i = top; i >= 1; i--)
	{
		printf("%d ",ans[i]);
	}
	printf("\n%d",dist[n]);
}
void begin()
{
	scanf("%d",&n);
	int p;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d",&p);
			if ( p > 0 )
			{
				add(i,j,p);
			}
		}
	}
}
int main()
{
	begin();
	spfa();
	end();
	return 0;
}