P3371 【模板】单源最短路径（弱化版） 最短路

题目：


思路：
模板题，练习一下
Dijkstra 算法（需要注意的是边权不能是负数
暴力算法：

#include<cstdio>
#include <iostream>
#include<cstring>
#include<algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=51111;
const int anss=(1<<31)-1;
typedef pair<int,int> pii;
vector <pii> e[10*maxn];
int n,m,s,day[maxn],dis[maxn];
bool vis[maxn];
int main()
{
    cin>>n>>m>>s;for(int i=1;i<=m;i++){
    int x,y,w;cin>>x>>y>>w;if(x==y) continue;e[x].push_back({
    y,w});}memset(dis,0x3f,sizeof(dis));dis[s]=0;for(int i=1;i<=n;i++){
    int tempy=0,tempw=0x3f3f3f3f;for(int j=1;j<=n;j++){
    if(!vis[j]&&dis[j]<tempw) tempy=j,tempw=dis[j];}//cout<<tempy<<endl;vis[tempy]=1;//cout<<tempy<<endl;for(auto to:e[tempy]){
    dis[to.first]=min(dis[to.first],tempw+to.second);//cout<<"to.first="<<to.first<<" "<<"dis[to.first]"<<dis[to.first]<<endl;}}for(int i=1;i<=n;i++) if(!vis[i]) dis[i]=anss;for(int i=1;i<=n;i++) cout<<dis[i]<<" ";cout<<endl;return 0;
}

优先队列版本：

#include<cstdio>
#include <iostream>
#include<cstring>
#include<algorithm>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=51111;
const int anss=(1<<31)-1;
struct node
{
    int x,dis;bool operator >(const node &a)const{
    if(dis==a.dis) return x<a.x;return dis>a.dis;}
};
priority_queue <node,vector<node>,greater<node>> q;
typedef pair<int,int> pii;
vector <pii> e[10*maxn];
int n,m,s,day[maxn],dis[maxn];
bool vis[maxn];
int main()
{
    cin>>n>>m>>s;for(int i=1;i<=m;i++){
    int x,y,w;cin>>x>>y>>w;if(x==y) continue;e[x].push_back({
    y,w});}memset(dis,0x3f,sizeof(dis));dis[s]=0;q.push({
    s,0});while(!q.empty()){
    int temp=q.top().x;q.pop();if(vis[temp]) continue;vis[temp]=1; //cout<<"!!"<<temp<<endl;for(auto to:e[temp]){
    dis[to.first]=min(dis[to.first],dis[temp]+to.second);//cout<<"to.first="<<to.first<<" "<<"dis[to.first]"<<dis[to.first]<<endl;q.push({
    to.first,dis[to.first]});}}for(int i=1;i<=n;i++) if(!vis[i]) dis[i]=anss;for(int i=1;i<=n;i++) cout<<dis[i]<<" ";cout<<endl;return 0;
}