看到题目首先就虎躯一震，不擅长图…
看完题目后感觉的单源最短路径算法就是Dijkstra了吧。下面大概讲一下Dijkstra的思路。
Dijkstra算法讲解有很多，大致的思路就是假设从1点出发，从1出发到达每一个点都有一个距离值（到不了自己定一个较大值替换）。假设当前点为i，已经选择过的点集为G（i已经在G中），那么到达其他一个其他点最小距离，要么是从G中其他点连接（即已经计算过的值），要么是从当前点i过去！然后从未选过的点挑选出G能到达且距离最短的点作为下一个选择的点，依次到结束。因为每一次选择的都是G可达最短的点，所以一定是最优的。具体看Dijkstra其他人的讲解吧。
如果什么都不想直接实现也是可以的，但是无法满分，只能得到80分
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int to,value; //to为子节点，value为父亲节点到子节点的距离
}node;
vector<node>vec[20002]; //vector建图
int n,m,value;
int v[20002]={0},pre[20002]; //v为记录是否到达过，pre记录点i最优解父亲节点是谁
int dis[20002]={0}; //从1到达i的最短长度
const int inf=0x3f3f3f;
int main(){
int tmp1,tmp2;
node date;
scanf("%d%d",&n,&m);
for(int t=1;t<=m;t++){
scanf("%d%d%d",&tmp1,&tmp2,&value);
date.to=tmp2;
date.value=value;
vec[tmp1].push_back(date);
}
for(int i=2;i<=n;i++){ //初始化除了1是0其他全是正无穷
dis[i]=inf;
}
for(int i=1;i<=n;i++){ //父亲节点初始化全是自己
pre[i]=i;
}
v[1]=1;
int choosepoint=1; //当前节点
for(int i=0;i<vec[choosepoint].size();i++){ //先单独计算从1出发
if(dis[vec[choosepoint][i].to]>vec[choosepoint][i].value+dis[choosepoint]){
dis[vec[choosepoint][i].to]=vec[choosepoint][i].value+dis[choosepoint];
pre[vec[choosepoint][i].to]=choosepoint; //更新子节点的父亲节点，其实在这里不用也无所谓...
}
}
for(int t=1;t<n;t++){
int tmppoint,minvalue=inf;
for(int p=1;p<=n;p++){ //找到下一个选择点
if(v[p]==0&&dis[p]<minvalue){
tmppoint=p;
}
}
choosepoint=tmppoint;
v[choosepoint]=1;
for(int i=0;i<vec[choosepoint].size();i++){ //用下一个节点更新未选过点的距离值
if(dis[vec[choosepoint][i].to]>vec[choosepoint][i].value+dis[choosepoint]){
dis[vec[choosepoint][i].to]=vec[choosepoint][i].value+dis[choosepoint];
pre[vec[choosepoint][i].to]=choosepoint;
}
}
}
for(int i=2;i<=n;i++){
cout<<dis[i]<<endl;
}
return 0;
}但是这里n<=20000，m<=200000数据规模是不行的。查资料有一个SPFA算法，其实就是Dijkstra的优化。
我们再回头看一下Dijkstra的特点，每次更新每个点距离值以后找到最小值，那么我们换一种思路。既然题目中说了没有负数环，那么假定从1出发到当前点i，那么可能通过点i更新后到其他点距离变短，如果每碰到距离变短的点就更新1到其他点距离，再碰到变小的点再更新一直到所有点没有可以松弛的点，是不是就是最优解了？
就相当于Dijkstra每次选择一个点，我保证1到达这个点的距离已经确定了，SPFA算法就是不断更新松弛，不保证当前点值已经是最好，一直在更新出现更小值后更新其他点，直到无点可以松弛就是最优解。
直接看代码吧，很好懂~
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int to,value; //to为子节点，value为父亲节点到子节点的距离
}node;
vector<node>vec[20002]; //vector建图
int n,m,value;
int v[20002]={0}; //v为记录是否在队列之中
int dis[20002]={0}; //从1到达i的最短长度
const int inf=0x3f3f3f; //假定的无穷值
queue<int>que; //SPFA算法中的队列
void SPFA(){
while(!que.empty()){
int now=que.front(); //松弛的当前点
que.pop();
v[now]=0;
for(int i=0;i<vec[now].size();i++){
if(v[vec[now][i].to]==0&&dis[vec[now][i].to]>dis[now]+vec[now][i].value){ //如果 队列中不存在且该点被松弛了
que.push(vec[now][i].to); //入队列
dis[vec[now][i].to]=dis[now]+vec[now][i].value; //更新
v[vec[now][i].to]=1; //标记
}
}
}
}
int main(){
int tmp1,tmp2;
node date;
scanf("%d%d",&n,&m);
for(int t=1;t<=m;t++){
scanf("%d%d%d",&tmp1,&tmp2,&value);
date.to=tmp2;
date.value=value;
vec[tmp1].push_back(date);
}
for(int i=2;i<=n;i++){ //初始化除了1是0其他全是正无穷
dis[i]=inf;
}
que.push(1);
v[1]=1;
SPFA();
for(int i=2;i<=n;i++){
cout<<dis[i]<<endl;
}
return 0;
}希望帮助到大家！