传送门：P1629
我用了n次dijkstra堆优化，不出所料超时了，题目说是单行道也就是有向图，请问怎么优化比较好。

代码如下 (TLE60%)

#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int edge[1005][1005];
 int dis[1005];
 int vis[1005];
 int n,m;
 int u,v,w;
 struct node
 {
 	int pos;
 	int d;
 	bool operator<(const node&nd)const 
 	{
 		return d>nd.d;
	 }
 };
 priority_queue<node>q;//默认大根堆 
 void Dijkstra(int s)
 {
 	memset(dis,127,sizeof(dis));
 	memset(vis,0,sizeof(vis));
    dis[s]=0;
    node nn;
    nn.pos=s;
    nn.d=dis[s];
    q.push(nn);
    while(!q.empty())
    {
    	node newnd=q.top();
    	q.pop();
    	int x=newnd.pos;
    	if(vis[x])continue;
    	vis[x]=1;
    	for(int i=1;i<=n;i++)
    	{
    		if(dis[i]>edge[x][i]+newnd.d)
			{
			dis[i]=edge[x][i]+newnd.d;
			node ndd;
			ndd.pos=i;
			ndd.d=dis[i];
			q.push(ndd);
		}
		}
	}
 }
 int main()
 {
 	cin>>n>>m;
 	memset(edge,127,sizeof(edge));
 	for(int i=1;i<=m;i++)
 	{
 		cin>>u>>v>>w;
 		edge[u][v]=min(edge[u][v],w);
	 }
	 Dijkstra(1);
	 long long ans=0;
	 for(int i=2;i<=n;i++)
	 ans+=dis[i];
	 for(int i=2;i<=n;i++)
	 {
	 	Dijkstra(i);
	 	ans+=dis[1];
	 }
	 cout<<ans<<endl;
	//单行所以不能这么算 
	return 0;
  }