[最短路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++中的回调函数简单介绍
相关内容
热门资讯
一分钟了解！We poker辅...
一分钟了解！We poker辅助器下载，aapoker怎么设置提高好牌几率，窍门教程（有挂透明挂）暗...
指南书辅助!美猴王房卡辅助!科...
指南书辅助!美猴王房卡辅助!科普真的有辅助挂(有挂方略)1、在美猴王房卡辅助插件功能辅助器技巧中，中...
8分钟了解！cloudpoke...
8分钟了解！cloudpoker外挂，xpoker怎么作弊，演示教程（有挂教学）1、首先打开xpok...
指南书辅助!威信茶馆修改器!了...
指南书辅助!威信茶馆修改器!了解存在有辅助方法(证实有挂)1、用户打开应用后不用登录就可以直接使用，...
第十分钟了解！wepokerp...
第十分钟了解！wepokerplus脚本，hardrock作弊，策略教程（有挂总结）1、wepoke...
方式辅助!川娱竞技血战辅助器!...
方式辅助!川娱竞技血战辅助器!有挂有辅助教程(揭秘有挂)1、打开软件启动之后找到中间准星的标志长按。...
第六分钟了解！impoker辅...
第六分钟了解！impoker辅助，拱趴大菠萝挂哪里，法门教程（有挂解惑）1）拱趴大菠萝挂哪里有没有挂...
举措辅助!丰城双剑辅助器是真的...
举措辅助!丰城双剑辅助器是真的吗!开挂是真的有辅助工具(讲解有挂)丰城双剑辅助器是真的吗脚本下载中分...
四分钟了解！约局吧作弊脚本，h...
四分钟了解！约局吧作弊脚本，hhpoker免费透视脚本，技法教程（有挂透明挂）1、很好的工具软件，可...
法门辅助!大当家辅助脚本下载!...
法门辅助!大当家辅助脚本下载!推荐有辅助攻略(果真有挂)一、大当家辅助脚本下载游戏安装教程牌型概率发...