给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式 共n-1行，第i行表示1号点到i+1号点的最短路。 样例输入 3 31 2 -1
2 3 -1
3 1 2 样例输出 -1
-2 数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int Max=20005;
struct Node{
int v;
int w;
};
vector<Node>vec[Max];
queue<int>que;
int dist[Max];
bool vis[Max];
int out[Max];
void init(int s,int e,int w){
Node node;
node.v=e;
node.w=w;
vec[s].push_back(node);
return;
}
bool SPFA(int s,int n){
que.push(s);
vis[s]=true;
dist[s]=0;
while(!que.empty())
{
int top=que.front();
que.pop();
vis[top]=false;
out[top]++;
if(out[top]>n) return false;
int size=vec[top].size();
for(int i=0;i<size;i++)
{
int v=vec[top][i].v;
int w=vec[top][i].w;
if(dist[v]>dist[top]+w)
{
dist[v]=dist[top]+w;
if(!vis[v])
{
que.push(v);
vis[v]=true;
}
}
}
}
return true;
}
int main(){
//freopen("E://1001.txt","r",stdin);
//input & initial
int n,m;//节点个数,边个数
cin>>n>>m;
for(int i=1;i<=n;i++)
{
Node node;
node.v=i;
node.w=0;
vec[i].push_back(node);
dist[i]=INT_MAX;
vis[i]=0;
out[i]=0;
}
for(int i=1;i<=m;i++)
{
int s,e,w;
cin>>s>>e>>w;
init(s,e,w);
}
//SPFA
int start=1;
if( SPFA(start,n)==false )
{
//cout<<"有负环"<<endl;
}
else
{
//cout<<"无负环"<<endl;
}
//output
for(int i=2;i<=n;i++)
{
cout<<dist[i]<<endl;
}
cout<<endl;
}