[最短路dijkstra]，启动！！！

总时间复杂度为 O ( ( n + m ) log ⁡ m ）

P4779 【模板】单源最短路径（标准版）

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e5+5;
int n,m,s;
vector<PII> v[N];
int dis[N];
bool vis[N];
void dijkstra(int s)
{priority_queue<PII,vector<PII>,greater<PII> > q;//for(int i=1;i<=n;i++) dis[i] = 1e9;q.push({0,s});//dis[s] = 0;while(q.size()){auto t = q.top();//q.pop();int now = t.se;//if(vis[now]==1) continue;//vis[now] = 1;//for(auto tt:v[now]){int spot = tt.fi,w = tt.se;if(dis[spot]>dis[now]+w){dis[spot] = dis[now]+w;q.push({dis[spot],spot});//}}}
}
int main()
{IOS;cin>>n>>m>>s;while(m--){int a,b,w;cin>>a>>b>>w;v[a].pb({b,w});} dijkstra(s);for(int i=1;i<=n;i++) cout<<dis[i]<<' ';return 0;
}

P3905 道路重建

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+5;
int n,m,A,B;
int va[10005][10005];
vector<PII> v[N];
int dis[N];
bool vis[N];
void dijkstra(int s)
{priority_queue<PII,vector<PII>,greater<PII> > q;for(int i=1;i<=n;i++) dis[i] = 1e9;dis[s] = 0;q.push({0,s});while(q.size()){auto t = q.top();q.pop();int now = t.se;if(vis[now]==1) continue;vis[now] = 1;for(auto tt:v[now]){int spot = tt.fi,w = 0;if(va[now][spot]==1) w = tt.se;if(dis[spot]>dis[now]+w){dis[spot] = dis[now]+w;q.push({dis[spot],spot});}	}}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,w;cin>>a>>b>>w;v[a].pb({b,w});v[b].pb({a,w});}	int d;cin>>d;while(d--){int a,b;cin>>a>>b;va[a][b] = 1;va[b][a] = 1;	}cin>>A>>B;dijkstra(A);cout<<dis[B];
}

P4554 小明的游戏

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair< int,pair<int,int> >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e4+5;
int n,m,s,stx,sty,edx,edy;
int dis[N][N];
bool vis[N][N];
char va[N][N];
int dx[4] ={0,0,1,-1};
int dy[4] ={1,-1,0,0};
void distra()
{priority_queue<PII,vector<PII>,greater<PII> > q;//for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dis[i][j] = 1e9;vis[i][j] = 0;}}q.push({0,{stx,sty}});//dis[stx][sty] = 0;while(q.size()){auto t = q.top();//q.pop();auto now = t.se;//int x = now.fi,y = now.se;if(vis[x][y]==1) continue;//vis[x][y] = 1;//for(int i=0;i<=3;i++){int xx = x+dx[i],yy = y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m){int w = 0;if(va[x][y]!=va[xx][yy]) w = 1;if(dis[xx][yy]>dis[x][y]+w){dis[xx][yy] = dis[x][y]+w;q.push({dis[xx][yy],{xx,yy}});//}}}}
}
int main()
{IOS;while(1)    {cin>>n>>m;if(n==0&&m==0) break;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>va[i][j];}}cin>>stx>>sty>>edx>>edy;stx += 1;sty += 1;edx += 1;edy += 1;distra();cout<<dis[edx][edy]<<"\n";}
}