在NOIP比赛中，如果出图论题最短路径应该是个常考点。
求解最短路径常用的算法有：Floyed算法（O(n^3)的暴力算法，在比赛中大概能过三十分）
dijkstra算法 （堆优化之后是O(MlogE),再加些玄学优化一般就是正解了，100分做法）
SPFA算法 （ 个人是不建议学习的，在NOIP提高组中出题人是故卡SPFA,它的复杂度是不确定的，它是基于ballman-Fold算法（O(N*E)）的队列优化版）
这个应该都是比较简单的，直接上代码吧
dijkstra
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define MAXN 500010
using namespace std;
int cnt,n,m,s;
int head[MAXN];
int d[MAXN]; struct Edge{
int s,t,w,next;
}edge[500010]; void add(int u,int v,int wi){
cnt++;
edge[cnt].s=u;
edge[cnt].t=v;
edge[cnt].w=wi;
edge[cnt].next=head[u];
head[u]=cnt;
} struct HeapNode{
int pos,dis;
bool operator < ( const HeapNode &a )const {
return a.dis<dis;
}
}; void dijkstra(){
priority_queue <HeapNode> Q;
for(int i=1;i<=n;i++) d[i]=2147483647;
d[s]=0;
Q.push((HeapNode){s,0});
while(!Q.empty()){
while(Q.size() > 1 && Q.top().dis != d[Q.top().pos]) Q.pop();
HeapNode tmp=Q.top();
Q.pop();
int u=tmp.pos;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].t;
int wi=edge[i].w;
if(d[v]>d[u]+wi){
d[v]=d[u]+wi,
Q.push((HeapNode) {v,d[v]});
}
}
} } int main(){ scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int x,y,z; scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
dijkstra();
for(int i=1;i<=n;i++){
printf("%d ",d[i]);
} return 0;
}
SPFA
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=10010;
int cnt,n,m,s;
int head[MAXN];
int d[MAXN];
int b[MAXN];
struct Edge{
int s,t,w,next;
}edge[500010]; void add(int u,int v,int wi){
cnt++;
edge[cnt].s=u;
edge[cnt].t=v;
edge[cnt].w=wi;
edge[cnt].next=head[u];
head[u]=cnt; } void spfa(){
queue<int>q;
for(int i=1;i<=n;i++){
d[i]=2147483647;
b[i]=0;
}
q.push(s);d[s]=0;b[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
b[u]=0;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].t;
if(d[v]>d[u]+edge[i].w){
d[v]=d[u]+edge[i].w;
if(b[v]==0){
b[v]=1;
q.push(v);
}
}
}
}
}
int main(){ scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
spfa();
for(int i=1;i<=n;i++){
printf("%d ",d[i]);
}
return 0;
}