会python真的可以为所欲为0(回)
371天前
这里还有人吗1(回)
556天前这里还有人吗0(回)
556天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
781天前到处都是羊，不想上班0(回)
861天前
鸽子
0(回)
865天前
dijkstra 和 spfa.rar(免费下载)[0 次下载]#include<stdio.h> |
#include<string.h> |
#include<vector> |
#include<queue> |
using namespace std; |
const int maxn = 500 + 5; |
const int INF = 1e8; |
struct Node |
{ |
int id; |
int dis; |
Node(int _id,int _dis):id(_id),dis(_dis){} |
bool operator < (const Node &b)const |
{ |
return dis > b.dis; |
} |
}; |
vector<Node> G[maxn]; |
int dis[maxn]; |
int vis[maxn]; |
void init() |
{ |
for(int i = 0;i < maxn;i++) |
{ |
vis[i] = 0; |
dis[i] = INF; |
G[i].clear(); |
} |
} |
void dijkstra(int v0)//找点，稠密图 |
{ |
dis[v0] = 0; |
priority_queue<Node> pq; |
pq.push(Node(v0,0)); |
while(!pq.empty()) |
{ |
Node ct = pq.top(); |
pq.pop(); |
if(vis[ct.id]) continue; |
vis[ct.id] = 1; |
for(int i = 0;i < G[ct.id].size();i++) |
{ |
Node nt = G[ct.id][i]; |
if(vis[nt.id]) continue; |
if(dis[nt.id] > dis[ct.id] + nt.dis) |
{ |
dis[nt.id] = dis[ct.id] + nt.dis; |
pq.push(Node(nt.id,dis[nt.id])); |
} |
} |
} |
} |
void spfa(int v0)//找一遍边，稀疏图 |
{ |
queue<int> q; |
q.push(v0); |
vis[v0] = 1; |
dis[v0] = 0; |
while(!q.empty()) |
{ |
int ct = q.front(); |
q.pop(); |
vis[ct] = 0; |
for(int i = 0;i < G[ct].size();i++) |
{ |
Node nt = G[ct][i]; |
if(dis[nt.id] > dis[ct] + nt.dis) |
{ |
dis[nt.id] = dis[ct] + nt.dis; |
if(!vis[nt.id]) |
{ |
vis[nt.id] = 1; |
q.push(nt.id); |
} |
} |
} |
} |
} |
int main() |
{ |
int N,M; |
while(scanf("%d%d",&N,&M) != EOF) |
{ |
init(); |
for(int i = 0;i < M;i++) |
{ |
int A,B,X; |
scanf("%d%d%d",&A,&B,&X); |
G[A].push_back(Node(B,X)); |
G[B].push_back(Node(A,X)); |
} |
int s,e; |
scanf("%d%d",&s,&e); |
//dijkstra(s);//78ms |
spfa(s);//0ms |
if(dis[e] != INF) |
printf("%d\n",dis[e]); |
else |
printf("-1\n"); |
} |
return 0; |
} |
dijkstra 和 spfa.rar(免费下载)[0 次下载]
