测评地址： https://www.luogu.org/problemnew/show/P3371
一、Dijkstra
测评结果：https://www.luogu.org/recordnew/show/18342452
提交AC

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 2147483647 //题目要求 
int u[500100],v[500100],w[500100],first[1000100],next[500100];
int d[10100],vis[10100];
int n,m,s,i,j,k;
int findmin(){//找剩下的最小值，返回点
	int i,k,min=INF;
	for(i=1;i<=n;i++)
		if(vis[i]==0 && d[i]<min){
			min=d[i];
			k=i;
		}
	return k;
}
int main(){
	cin>>n>>m>>s;
	for(i=1;i<=n;i++) d[i]=INF;
	d[s]=0;
	vis[s]=1;
	memset(first,-1,sizeof(first));
	memset(next,-1,sizeof(next));
	for(i=1;i<=m;i++){//边读取
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
		next[i]=first[u[i]];
		first[u[i]]=i;
		if(u[i]==s && d[v[i]]>w[i]) d[v[i]]=w[i];
	}
	for(i=1;i<=n-1;i++){//n-1次循环
		k=findmin();
		vis[k]=1;
		j=first[k];//j是边
		while(j!=-1){
			if(vis[v[j]]==0 && d[k]+w[j]<d[v[j]])
				d[v[j]]=d[k]+w[j];
			j=next[j];
		}
	}
	printf("%d",d[1]);
	for(i=2;i<=n;i++) printf(" %d",d[i]);
	return 0;
}

二、多源最短路径 Floyd
提交0分

//多源最短路径 floyd
#include<iostream>
using namespace std;
int e[1000][1000];
#define INF 214748364
int i,j,k,n,m,w;//n点m边 w边长 
int s;//出发点 
void print_graph()
{
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)
            cout<<e[i][j]<<' ';
        cout<<endl;
    }
}
void print_dist()
{
	for(i=1;i<=n;i++)
		cout<<e[s][i]<<" ";	
} 
void floyd() 
{
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(e[i][j]>e[i][k]+e[k][j])
                    e[i][j]=e[i][k]+e[k][j];
}
void init_1()//初始化 
{
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) e[i][j]=INF;
}
void init_2()//初始化 
{
    for(i=1;i<=n;i++) e[i][i]=0;
}
void input_graph()//矩阵输入数据 
{
    for(k=1;k<=m;k++){
        cin>>i>>j>>w;
        e[i][j]=w;
    }
}
int main()
{
    cin>>n>>m>>s;
    init_1();
    input_graph();
    init_2();
//	print_graph(); cout<<endl;
    floyd();
//	print_graph(); 
	print_dist();
}

三、bellman-ford

1、提交60分（3个点超时）
测评结果：https://www.luogu.org/recordnew/show/18344308

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 501000
#define INF 99900999//改为2147483647后得0分
int u[maxn],v[maxn],w[maxn],d[maxn];
int n,m;
int main(){
    int i,j;
    int tmp;
    cin>>n>>m>>tmp;//n点 m边 
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&u[i],&v[i],&w[i]);//起 终 权 
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[tmp]=0;
    for(i=1;i<=n-1;i++)
        for(j=1;j<=m;j++)
            if(d[v[j]]>d[u[j]]+w[j])//v终 u起 w是u->v 
                d[v[j]]=d[u[j]]+w[j];
    for(i=1;i<=n;i++)
        printf("%d ",d[i]);
    return 0;
}

2、提交90分（无法到达的测试点未过，改为2147483647后得0分）
测评结果：https://www.luogu.org/recordnew/show/18344389

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 501000
#define INF 99900999
int u[maxn],v[maxn],w[maxn],d[maxn];
int n,m,check,s;
int main(){
    int i,j;
    cin>>n>>m>>s;
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[s]=0;
    for(i=2;i<=n;i++){
        check=1;
        for(j=1;j<=m;j++)
            if(d[v[j]]>d[u[j]]+w[j]){
                d[v[j]]=d[u[j]]+w[j];
                check=0;
            }
        if(check)
            break;//防止超时
    }
    for(i=1;i<=n;i++)
        printf("%d ",d[i]);
    return 0;
}

3、提交AC
测评结果：https://www.luogu.org/recordnew/show/18344981
为啥2147483647没超过int范围，还是会错，出现负值…

#include<iostream>
using namespace std;
#define maxn 501000
#define INF 2147483647
int u[maxn],v[maxn],w[maxn];
long long d[maxn];//long long 防止出现负值 
int n,m,s,i,j;
int main(){
    cin>>n>>m>>s;//n点 m边 s出发点 
    for(i=1;i<=m;i++) cin>>u[i]>>v[i]>>w[i];//起 终 权 
    for(i=1;i<=n;i++) d[i]=INF;//初始化 
    d[s]=0;
    for(i=2;i<=n;i++){
        int check=1;
        for(j=1;j<=m;j++)
            if(d[v[j]]>d[u[j]]+w[j]){
                d[v[j]]=d[u[j]]+w[j];
                check=0;
            }
        if(check) break;//优化，防止超时 
    }
    for(i=1;i<=n;i++) cout<<d[i]<<" "; 
    return 0;
}