|
|
思路： 就是一個最短路徑的問題。但是題目數據規模跟描述不符合。 數組要開大一些才能過。官方數據是描述是符合的，可能是管理員加了一些進去。
 #include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_E 4096
#define MAX_V 2048
#define MAX_COST (1 << 30)
  struct edge_node  {
 int idx, cost;
struct edge_node *next;
 };
struct graph_node {
struct edge_node edges[MAX_E], *map[MAX_V];
int edges_cnt, vertexs_cnt;
int min_dis[MAX_V];
};
inline int min(int a, int b)
{
return a < b ? a : b;
}
inline void graph_init(struct graph_node *g, int vertexs_cnt)
{
g->vertexs_cnt = vertexs_cnt;
g->edges_cnt = 0;
memset(g->map, 0, vertexs_cnt * sizeof(g->map[0]));
}
inline void graph_addedge(struct graph_node *g,
int from, int to,
int cost
)
{
struct edge_node *e;
e = &g->edges[g->edges_cnt++];
e->idx = to;
e->cost = cost;
e->next = g->map[from];
g->map[from] = e;
}
inline void graph_spfa(struct graph_node *g, int idx)
{
static int queue[MAX_V], vis[MAX_V], tm, head, tail;
int i, val;
struct edge_node *e;
for (i = 0; i < g->vertexs_cnt; i++)
g->min_dis[i] = MAX_COST;
g->min_dis[idx] = 0;
head = tail = 0;
tm++;
queue[tail++] = idx;
  while (head != tail) {
idx = queue[head++];
vis[idx] = 0;
for (e = g->map[idx]; e; e = e->next) {
val = g->min_dis[idx] + e->cost;
if (val >= g->min_dis[e->idx])
continue;
g->min_dis[e->idx] = val;
if (vis[e->idx] == tm)
continue;
queue[tail++] = e->idx;
vis[e->idx] = tm;
 }
}
}
int main()
{
static int loc[MAX_V], i, F, C, P, M, from, to, cost, cnt;
static struct graph_node g;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d%d", &F, &P, &C, &M);
graph_init(&g, F + 1);
while (P--) {
scanf("%d%d%d", &from, &to, &cost);
graph_addedge(&g, from, to, cost);
graph_addedge(&g, to, from, cost);
}
for (i = 0; i < C; i++)
scanf("%d", &loc[i]);
graph_spfa(&g, 1);
cnt = 0;
for (i = 0; i < C; i++)
cnt += (g.min_dis[loc[i]] <= M);
printf("%d\n", cnt);
for (i = 0; i < C; i++)
if (g.min_dis[loc[i]] <= M)
printf("%d\n", i + 1);
return 0;
}
|