[最短路dijkstra]，启动！！！
创始人
2024-11-05 02:35:35
0次
总时间复杂度为 O ( ( n + m ) log m ）
P4779 【模板】单源最短路径（标准版）
#include #define ll long long #define fi first #define se second #define pb push_back #define PII pair #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 v[N]; int dis[N]; bool vis[N]; void dijkstra(int s) { priority_queue,greater > 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< P3905 道路重建
#include #define ll long long #define fi first #define se second #define pb push_back #define PII pair #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 v[N]; int dis[N]; bool vis[N]; void dijkstra(int s) { priority_queue,greater > 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< P4554 小明的游戏
#include #define ll long long #define fi first #define se second #define pb push_back #define PII pair< int,pair > #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,greater > 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<
上一篇：C++中的回调函数简单介绍
相关内容
热门资讯
微扑克wpk透视辅助(微扑克)...
微扑克wpk透视辅助(微扑克)wpk微扑克真的有辅助插件吗(透视)本来存在有挂(详细辅助解说技巧)一...
wepokeai代打的胜率(透...
wepokeai代打的胜率(透视)wepoke软件透明挂辅助(详细辅助大神讲解)果然真的有挂(玩家辅...
微扑克wpk透视辅助(微扑克)...
微扑克wpk透视辅助(微扑克)微扑克有辅助挂吗(透视)果然有挂(详细辅助力荐教程)1、用户打开应用后...
wepoke计算辅助(透视)w...
wepoke计算辅助(透视)wepoke有正规吗(详细辅助2025新版教程)本来有挂(可靠真的有挂)...
微扑克辅助挂(微扑克)微扑克软...
微扑克辅助挂(微扑克)微扑克软件的规律(透视)一贯是真的有挂(详细辅助揭秘教程)；进入游戏-大厅左侧...
wepoke模拟器(透视)we...
wepoke模拟器(透视)wepoke是不是有挂(详细辅助玩家教程)总是有挂(大神辅助德之星)1.w...
微扑克wpk透视辅助(微扑克)...
微扑克wpk透视辅助(微扑克)微扑克系统机制(透视)一贯是有挂(详细辅助微扑克教程)1）微扑克wpk...
wepoke辅助挂(透视)we...
wepoke辅助挂(透视)wepoke游戏辅助工具(详细辅助曝光教程)总是存在有挂(玩家辅助)；1、...
wepoke是真的有挂(透视)...
wepoke是真的有挂(透视)wepower使用说明书(详细辅助技巧教程)真是真的有挂(可靠一定有挂...
微扑克有辅助挂(微扑克)德州微...
微扑克有辅助挂(微扑克)德州微扑克外挂是真的吗(透视)一直是有挂(详细辅助技巧教程)1、金币登录送、...