反向建图+小根堆+dijkstra=正解 （手敲）

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
priority_queue<pair<int,int> >q;//第一维是dist的相反数，第二维是节点编号 
priority_queue<pair<int,int> >q2;//第一维是dist的相反数，第二维是节点编号 
int maxx;
int d1[1110];
int d2[1110];
bool visited[1110];
int n,m,x;
struct tedge{
	int to,len;
};
vector<tedge>ed[100010];
vector<tedge>ed2[100010];
void add_edge1(int u,int v,int w)
{
	tedge tmp;
	tmp.to=v;
	tmp.len=w;
	ed[u].push_back(tmp);
}
void add_edge2(int u,int v,int w)
{
	tedge tmp;
	tmp.to=v;
	tmp.len=w;
	ed2[u].push_back(tmp);
}
void dijkstra1();
void dijkstra2();
int main()
{
	int a,b,t;
	scanf("%d%d%d",&n,&m,&x);
	for (int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add_edge1(u,v,w);
		add_edge2(v,u,w);
		
		/*for (int j=0;j<ed[u].size();j++)
		{
			printf("%d->%d:%d\n",u,ed[u][j].to,ed[u][j].len);
		}*/
	}//建图 
	for (int i=1;i<=m;i++)
	{
		for (int j=0;j<ed[i].size();j++)
		{
			//printf("%d->%d:%d\n",i,ed[i][j].to,ed[i][j].len);
		}
	}
	dijkstra1();
	
	dijkstra2();
	for (int i=1;i<=n;i++)
	{
		//printf("%d %d\n",d1[i],d2[i]);
		maxx=maxx>(d1[i]+d2[i])?maxx:(d1[i]+d2[i]);
	}
	printf("%d",maxx);
	return 0;
}
void dijkstra1()
{
	memset(d1,0x3f,sizeof(d1));
	memset(visited,0,sizeof(visited));
	d1[x]=0;
	q.push(make_pair(0,x));
	while (q.size())
	{
		int ii=q.top().second;
		q.pop();
		if (visited[ii])
			continue;
		visited[ii]=true;
		for (int i=0;i<ed[ii].size();i++)
		{
			if (d1[ed[ii][i].to]>d1[ii]+ed[ii][i].len)
			{
				d1[ed[ii][i].to]=d1[ii]+ed[ii][i].len;
				
				q.push(make_pair(-d1[ed[ii][i].to],ed[ii][i].to));
			}
		}
	}
}
void dijkstra2()
{
	memset(d2,0x3f,sizeof(d2));
	memset(visited,0,sizeof(visited));
	d2[x]=0;
	q2.push(make_pair(0,x));
	while (q2.size())
	{
		int ii=q2.top().second;
		q2.pop();
		if (visited[ii])
			continue;
		visited[ii]=true;
		for (int i=0;i<ed2[ii].size();i++)
		{
			if (d2[ed2[ii][i].to]>d2[ii]+ed2[ii][i].len)
			{
				d2[ed2[ii][i].to]=d2[ii]+ed2[ii][i].len;
				
				q2.push(make_pair(-d2[ed2[ii][i].to],ed2[ii][i].to));
			}
		}
	}
}