최단 루트 템플릿 요약
13187 단어 최단로
#include
#include
#include
#include
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
struct node
{
int to, w;
int next;
} data[maxn];
int cnt;
int head[maxn], dist[maxn];
void add(int u, int v, int w) {
data[cnt].to = v;
data[cnt].w = w;
data[cnt].next = head[u];
head[u] = cnt++;
}
void dijkstra(int s) {
memset(dist, inf, sizeof(dist));
priority_queueint, int> > q;
q.push(make_pair(0, s));
dist[s] = 0;
while(!q.empty())
{
int now = q.top().second;
q.pop();
for(int i = head[now]; ~i; i = data[i].next)
{
int u = data[i].to;
if(dist[u] > dist[now] + data[i].w)
{
dist[u] = dist[now] + data[i].w;
q.push(make_pair(-dist[u], u));
}
}
}
}
int main()
{
int n, m; //n m
cnt = 0;
scanf("%d %d", &m, &n);
memset(head, -1, sizeof(head));
for(int i = 0; i < m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
dijkstra(1);
printf("%d
", dist[n]);
}
전방향성+spfa
#include
#include
#include
#include
using namespace std;
const int maxn = 1e5 + 100;
const int inf = 0x3f3f3f3f;
struct node {
int v;
int w;
int next;
}e[maxn];
int head[maxn], cnt, dist[maxn];
bool vis[maxn];
void add(int u, int v, int w)
{
e[cnt].v = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
}
void spfa(int s, int t)
{
memset(vis, false, sizeof(vis));
memset(dist, inf, sizeof(dist));
queue<int> q;
q.push(s);
vis[s] = true;
dist[s] = 0;
while(!q.empty())
{
int now = q.front();
q.pop();
vis[now] = false;
for(int i = head[now]; ~i; i = e[i].next)
{
int v = e[i].v;
int w = e[i].w;
if(dist[v] > dist[now] + w)
{
dist[v] = dist[now] + w;
if(!vis[v])
{
q.push(v);
vis[v] = true;
}
}
}
}
printf("%d
", dist[t]);
}
int main()
{
int m, n;
scanf("%d %d", &m, &n);
memset(head, -1, sizeof(head));
cnt = 0;
for(int i = 0; i < m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
spfa(1, n);
}
vector + dijkstra
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e7;
int n, m, dist[1123];
vectorint , int> >e[1123];
void init()
{
for(int i = 0; i <= n; i++)
{
e[i].clear();
dist[i] = maxn;
}
}
void dijkstra()
{
priority_queueint, int> > q;
q.push(make_pair(0, 1));
while(!q.empty())
{
int now = q.top().second;
q.pop();
for(int i = 0; i < e[now].size(); i++)
{
int v = e[now][i].first;
if(dist[v] > dist[now] + e[now][i].second)
{
dist[v] = dist[now] + e[now][i].second;
q.push(make_pair(-dist[v], v));
}
}
}
}
int main()
{
int i, u, v, w;
scanf("%d %d", &m, &n);
init();
for(i = 0; i < m; i++)
{
scanf("%d %d %d", &v, &u, &w);
e[v].push_back(make_pair(u, w));
e[u].push_back(make_pair(v, w));
}
dist[1] = 0;
dijkstra();
printf("%d
", dist[n]);
}
vector+spfa
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e6;
int inq[1123], dist[1123], n, m;
vectorint, int> > e[1123];
void init()
{
for(int i = 0; i <= n; i++)
{
e[i].clear();
inq[i] = 0;
dist[i] = maxn;
}
}
void spfa()
{
queue<int> q;
q.push(1);
dist[1] = 0;
inq[1] = 1;
while(!q.empty())
{
int now = q.front();
q.pop();
inq[now] = 0;
for(int i = 0; i < e[now].size(); i++)
{
int v = e[now][i].first;
if(dist[v] > dist[now] + e[now][i].second)
{
dist[v] = dist[now] + e[now][i].second;
if(!inq[v])
{
q.push(v);
inq[v] = 1;
}
}
}
}
}
int main()
{
int i, u, v, w;
scanf("%d %d", &m, &n);
init();
for(i = 0; i < m; i++)
{
scanf("%d %d %d", &u, &v, &w);
e[u].push_back(make_pair(v, w));
e[v].push_back(make_pair(u, w));
}
spfa();
printf("%d
", dist[n]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Uva10986-Sending email텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.