阅读量:0
总时间复杂度为 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"; } } 