UVA 10986 - Sending email
8170 단어 email
dijkstra 코드:
#include<stdio.h>
#include<string.h>
#define INF 200000005
#define MAXD 20005
int u, v, w, S, T, n, m, N;
int d[MAXD][MAXD], f[MAXD];
bool vis[MAXD];
int min( int a, int b)
{
return a < b ? a : b;
}
void init()
{
for( int i = 0; i < n; i ++)
f[i] = ( i == S ? 0 : INF );
memset( vis, false, sizeof vis);
for( int i = 0; i < n; i ++)
for( int j = 0; j < n; j ++)
{
if( i == j) d[i][j] = 0;
else d[i][j] = INF;
}
for( int i = 0; i < m; i ++)
{
scanf( "%d%d%d", &u, &v, &w);
d[u][v] = d[v][u] = w;
}
}
void dijkstra()
{
for( int i = 0; i < n; i ++)
{
int x, tt = INF;
for( int y = 0; y < n; y ++)
if( !vis[y] && f[y] <= tt)
tt = f[ x = y];
vis[x] = true;
for( int y = 0; y < n; y ++) {
f[y] = min( f[y], f[x] + d[x][y]);
}
}
}
int main()
{
scanf( "%d", &N);
for( int cas = 1; cas <= N; cas ++)
{
scanf( "%d%d%d%d", &n, &m, &S, &T);
init();
dijkstra();
if( f[T] >= INF) printf( "Case #%d: unreachable
", cas);
else
printf( "Case #%d: %d
", cas, f[T]);
}
return 0;
}
다음은 Staginner의 SPFA를 참조하십시오.
#include<stdio.h>
#include<string.h>
#define MAXD 100005
#define INF 200000005
int N, n, m, S, T, e, a, b, c, cas;
int first[MAXD], next[MAXD], v[MAXD], w[MAXD], d[MAXD], q[MAXD];
bool inq[MAXD];
void input( int a, int b, int c)
{
v[e] = b;
w[e] = c;
next[e] = first[a];
first[a] = e;
e ++;
}
void init()
{
scanf( "%d%d%d%d", &n, &m, &S, &T);
memset( first, -1, sizeof first);
e = 0;
for( int i = 0; i < m; i ++)
{
scanf( "%d%d%d", &a, &b, &c);
input( a, b, c);
input( b, a, c);
}
}
void SPFA()
{
int front, rear, u;
front = rear = 0;
for( int i = 0; i < n; i ++)
d[i] = ( i == S ? 0 : INF);
q[rear ++] = S;
while( front != rear)
{
u = q[front ++];
if( front == n) front = 0;
inq[u] = false;
for( int i = first[u]; i != -1; i = next[i])
if( d[u] + w[i] < d[v[i]])
{
d[ v[i] ] = d[u] + w[i];
if( !inq[ v[i] ])
{
q[rear ++] = v[i];
if( rear == n) rear = 0;
inq[ v[i]] = true;
}
}
}
if( d[T] == INF)
printf( "Case #%d: unreachable
", cas);
else
printf( "Case #%d: %d
", cas, d[T]);
}
int main()
{
scanf( "%d", &N);
for( cas = 1; cas <= N; cas ++)
{
init();
SPFA();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Maizzle 및 Tailwind CSS를 사용한 이메일 마케팅이메일 마케팅은 이메일을 사용하여 비즈니스 제품 또는 서비스를 홍보하는 강력한 마케팅 채널입니다. 이메일 마케팅은 이메일 목록에 있는 고객에게 신제품, 할인 및 기타 서비스를 알릴 수 있는 마케팅의 한 형태입니다. ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.