栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 2394 Checking an Alibi

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 2394 Checking an Alibi

#include<cstdio>#include<cstring>const int maxn(555);int g[maxn][maxn];int dist[maxn], vis[maxn];int n, p, c, m;const int inf(100000000);int ans[maxn];void dijk(){memset(vis, 0, sizeof vis);for(int i = 1; i <= n; i ++) dist[i] = inf;dist[1] = 0;for(int i = 0; i < n; i ++){int min = inf, u;for(int j = 1; j <= n; j ++){if(!vis[j] && dist[j] < min){min = dist[j];u = j;}}if(min == inf) break;vis[u] = 1;for(int j = 1; j <= n; j ++){if(!vis[j] && g[u][j] != inf)  if(g[u][j] + dist[u] < dist[j])dist[j] = dist[u] + g[u][j];}}int cnt = 0;for(int i = 1; i <= c; i ++){int k;scanf("%d", &k);if(dist[k] <= m)  ans[cnt++] = i;}printf("%dn", cnt);for(int i = 0; i < cnt; i ++)  printf("%dn", ans[i]);}int main(){while(~scanf("%d%d%d%d", &n, &p, &c, &m)){for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)if(i == j) g[i][j] = 0;else g[i][j] = inf;for(int i = 0; i < p; i ++){int u, v, w;scanf("%d%d%d", &u, &v, &w);if(w < g[u][v]){     g[u][v] = g[v][u] = w;}}dijk();}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/374304.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号