C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-06-14

#include<iostream>
#include<vector>

using namespace std;

int main() {
	int INF_MAX = INT32_MAX;
	int N, M;
	cin >> N >> M;
	vector<int> people(N + 1, 0);
	vector<vector<int>> map(N + 1);

	for (int i = 1;i < N + 1;i++) {
		cin >> people[i];
	}

	for (int i = 0;i < M;i++) {
		int x, y;
		cin >> x >> y;
		map[x].push_back(y);
		map[y].push_back(x);
	}

	vector<int>  dist(N + 1, INF_MAX), visited(N + 1, 0);
	dist[1] = people[1];
	visited[1] = 1;
	for (int i = 1;i < N + 1;i++) {
		for (int i = 0;i < map[1].size();i++)
			dist[map[1][i]] = dist[1] + people[map[1][i]];
	}


	for (int i = 2;i < N + 1;i++) {
		int min = INF_MAX, pos;
		for (int k = 1;k < N + 1;k++) {
			if (visited[k] == 0 && dist[k] < min) {
				min = dist[k];
				pos = k;
			}
		}
		visited[pos] = 1;

		if (pos == N)
			break;

		for (int s = 0;s < map[pos].size();s++) {
			int p = map[pos][s];
			if ((visited[p] == 0) && ((min + people[p]) < dist[p])) {
				dist[p] = min + people[p];
			}
		}

	}

	cout << dist[N] << endl;
	return 0;
}

C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-06-13

#include <iostream>
using namespace std;
void dijstl(int start,int end,int **gonglu,int *cost,int *zhan,int m)
{
	
	int *s = new int[end];
	int *dis = new int[end];
	
	for (int i = 0; i < end; i++)
	{
		s[i] = 0;
		dis[i] = 99999;
	}
	s[start] = 1;
	dis[start] = zhan[start];
	
	int index = start;
	for (int j = 0; j < end; j++)
	{
		int minn = 99999;
		for (int i = 0; i < end; i++)
		{
			if (s[i] == 0)
			{
				if (dis[i] < minn)
				{
					minn = dis[i];
					index = i;
				}
			}
		}
		s[index] = 1;
		for (int i = 0; i < m; i++)
		{
			if (gonglu[i][0] == index)
			{
				if (dis[gonglu[i][0]] + zhan[gonglu[i][1]] < dis[gonglu[i][1]])
					dis[gonglu[i][1]] = dis[gonglu[i][0]] + zhan[gonglu[i][1]];
			}
			else if(gonglu[i][1] == index)
			{
				if (dis[gonglu[i][1]] + zhan[gonglu[i][0]] < dis[gonglu[i][0]])
					dis[gonglu[i][0]] = dis[gonglu[i][1]] + zhan[gonglu[i][0]];
			}
		}
		
	}
	for (int i = 0; i < end; i++)
		cost[i] = dis[i];
}
int main()
{
	int n, m;

	while (cin >> n >> m)
	{
		//int zhan[5];
		int *zhan = new int[n];
		int index=0;
		for (int i = 0; i<n; i++)
		{
			cin >> zhan[i];;
			index += zhan[i];
		}
		int **gonglu = new int*[m];
		//int gonglu[6][2];
		for (int i = 0; i<m; i++)
		{
			gonglu[i] = new int[2];
			cin >> gonglu[i][0] >> gonglu[i][1];
			gonglu[i][0]--;
			gonglu[i][1]--;
		}
		//int cost[5];
		int *cost=new int[n];
		dijstl(0, n, gonglu, cost, zhan,m);
		cout << cost[n-1] << endl;
	}
	return 0;
}