2,9，10 TLE，用Dijkstra算法，图用类似邻接表的结构，用vector构造二维数组，Map.arcs[a][b]即a->b的权值

如下是代码

#include <iostream>
#include <string.h>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <fstream>
#include <cstdlib>
using namespace std;

const int MaxInt = 2147483647;

class Node
{
public:
	int num;					//点的number
	int dist;					//distance

public:
	Node(int n, int d) :num(n), dist(d) {}
};
class Djk						//Dijkstra算法的结构
{
public:
	vector<bool> Found;			//S
	vector<int> D;				//sum_distance
	vector<int> Path;			//前驱
	int beg;					//出发点
};
class Map
//点是从0开始，所以要经过-1处理
{
public:
	vector<vector<Node> > arcs;	//图的本体
	int nodNum;					//node的个数
	int line;					//边数
	Djk ass;					//Djk的相关数据结构

public:
	Map(int n,int m,int s)		//构造函数，n为结点数，m为边数，s为初始点
	{
		nodNum = n;
		line = m;
		ass.beg = s-1;

		vector<Node> temp;
		for (int i = 0; i < nodNum; i++)		//初始化邻接表
		{
			arcs.push_back(temp);
		}
		for (int i = 0; i < nodNum; i++)		//初始化Di
		{
			ass.Found.push_back(false);
			ass.D.push_back(MaxInt);
			ass.Path.push_back(-1);
		}


		this->__init__line();			//初始化Dijkstra算法的结构
		this->__init__djs();

	}
	void add_line(int a,int b,int d)	//添加 a->b的边，权为d
	{
		for (size_t i = 0; i < arcs[a].size(); i++)
			if (arcs[a][i].num == b)
			{
				if (arcs[a][i].dist > d) arcs[a][i].dist = d;
				return;
			}
		arcs[a].push_back(Node(b, d));
	}
	int distAtoB(int a, int b)			//求出a->b的距离
	{
		for (size_t i = 0; i < arcs[a].size(); i++)
		{
			if (arcs[a][i].num == b)
				return arcs[a][i].dist;
		}
		return MaxInt;
	}
	void __init__line()					//初始化边（读入输入）
	{
		for (int i = 0; i < line; i++)
		{
			int a, b, d;
			cin >> a >> b >> d;
			this->add_line(a-1, b-1, d);
		}
	}
	
	void __init__djs()					//通过上面的信息初始化Dijkstra算法的结构
	{
		for (int i = 0; i < nodNum; i++)
		{
			ass.Found[i] = false;
			ass.D[i] = MaxInt;
			ass.Path[i] = -1;
		}
		for (size_t i = 0; i < arcs[ass.beg].size(); i++)		//写的比较套，就是把邻接表里面初始点的相邻点都初始化
		{
			ass.D[arcs[ass.beg][i].num] = arcs[ass.beg][i].dist;
			ass.Path[arcs[ass.beg][i].num] = ass.beg;
		}

		ass.Found[ass.beg] = true;
		ass.D[ass.beg] = 0;


		for (int i = 1; i < nodNum - 1; i++)
		{
			int v = -1;
			int min = MaxInt;

			for (int j = 0; j < nodNum; j++)
			{
				if (!ass.Found[j] && ass.D[j] < min)
				{
					v = j;
					min = ass.D[j];
				}
			}
			ass.Found[v] = true;

			for (int j = 0; j < nodNum; j++)
			{
				int a_b = distAtoB(v, j);
				if (!ass.Found[j] && a_b!=MaxInt && (ass.D[v] + a_b < ass.D[j]))
				{
					ass.D[j] = ass.D[v] + distAtoB(v, j);
					ass.Path[j] = v;
				}
			}
		}
	}
	void PrintD()			//输出Dijkstra算法的结构里面的D(Distance)
	{
		for (int i = 0; i < nodNum; i++)
		{
			cout << ass.D[i] << " ";
		}
	}
};
int main()
{
	int n, m, s;
	cin >> n >> m >> s;
	Map M(n, m, s);
	M.PrintD();
	return 0;
}