最小生成树 https://ac.nowcoder.com/acm/contest/26077/1008

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//typedef __int128 LL;//2的128
typedef long long ll; //2的64
// 1e9,, 1e19,,1e38
const int N=100010,M=500010;
int n,m,p[N];
int cnt,res;
struct EDGE
{
    int a,b,w;
    bool operator<(const EDGE & qwe)const
        {
            return w<qwe.w;
        }
}edge[M];
inline int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
}
void solve()
{
    cin>>n>>m;
        for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=m;i++)
    {
        int a,b,w; cin>>a>>b>>w;
            edge[i]={a,b,w};
    }
     res=0;//最小生成树的价值
     cnt=0;//生成树的边，，是否是生成树
    sort(edge+1,edge+1+m);
    for(int i=1;i<=m;i++)
    {
        int a=edge[i].a;
        int b=edge[i].b;
        int w=edge[i].w;
        a=find(a),b=find(b);
        if(a!=b)
            {
                p[a]=b;
                res+=w;
                cnt++;
            }
    }
}
int main()
{
    ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
    solve();
if(cnt==n-1)//是最小生成树
{
    cout<<res;
}
    return 0;
}

dijk() https://ac.nowcoder.com/acm/contest/26077/1007

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//typedef __int128 LL;//2的128
typedef long long ll; //2的64
// 1e9,, 1e19,,1e38
int dist[1010];
int n,m,s,t;
bool vis[1010];
struct node
{
    int w,id;
    bool operator<(const node & qwe) const
        {
            return w>qwe.w;
        }
};
vector<node>q[1010];
void dijk(int s)
{memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
priority_queue<node>w;
    w.push({0,s});
    while(w.size())
    {
        auto k=w.top();
        w.pop();
        int id=k.id;
        int dis=k.w;
        if(vis[id]) continue;
        vis[id]=1;
        //for(int i=0;i<q[id].size();i++)
        for( auto i : q[id])
        {
            int tx=i.id;            
            int ju=i.w;
            if(dist[tx]>dis+ju)
                    {
                        dist[tx]=dis+ju;
            w.push({dis+ju,tx});
                    }
        }       
    }
}
void solve()
{cin>>n>>m>>s>>t;
while(m--)
    {
        int a,b,v;
            cin>>a>>b>>v;
        q[a].push_back({v,b});
        q[b].push_back({v,a});  
    }
        dijk(s);
}
int main()
{
    ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
    solve();
    if(dist[t]>0x3f3f3f) cout<<-1;
    else 
cout<<dist[t];
    return 0;
}

https://ac.nowcoder.com/acm/contest/61132/H
自己建边的最短路问题

 #include<bits/stdc++.h>
using namespace std;
const int N=3010;
char s[N][N];
int n,m;
int w[N][N];
int nex[]={0,0,1,-1};
int ney[]={1,-1,0,0};
bool used[N][N];//已经到达过
struct node
{
int x,y,w;
    bool operator<(const node & qwe)const
        {
            return w>qwe.w;
        }   
};
int dijk()
{
    priority_queue<node>q;
    q.push({1,1,0});
    while(q.size())
    {
        auto k=q.top(); 
         q.pop();
    int len=k.w; int x=k.x,y=k.y;
    if(x==n&&y==m) return len;
    if(used[x][y]) continue;
    used[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int flag=0;
    int xx=0,yy=0;
    if(s[x][y]=='.')
    {
        flag=1;
        xx=x+nex[i];yy=y+ney[i];
    }
    else if(s[x][y]=='*')
        {
            xx=x+nex[i]*w[x][y];
            yy=y+ney[i]*w[x][y];
        }
        if(used[xx][yy]) continue;
        if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&s[xx][yy]!='#')
      q.push({xx,yy,len+flag});


    }   


    }
    return -1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>(s[i]+1);//下标1开始输入
    int t;
        cin>>t;
    while(t--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        w[a][b]=c;
    }
    int k=dijk();
    cout<<k;
    return 0;
}