慕课网电子商务网站开发,南阳高质量建设大城市网站,阿里云服务器可以做网站吗,柳市最好的网站建设公司题目
一个有向图#xff0c;求一点到所有点的最短距离
输入
4 6 1(4个点#xff0c;6条边#xff0c;从1出发) 1 2 2(1点到2点有一条权值2的线) 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4
输出
0 2 4 3 解题思路
这题数据非常的大 说明 时空限制#xff1a;1000ms,128M …题目
一个有向图求一点到所有点的最短距离
输入
4 6 1(4个点6条边从1出发) 1 2 2(1点到2点有一条权值2的线) 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4
输出
0 2 4 3 解题思路
这题数据非常的大 说明 时空限制1000ms,128M 数据规模 对于20%的数据N5M15 对于40%的数据N100M10000 对于70%的数据N1000M100000 对于100%的数据N10000M500000 所以我们用SPFA算法用邻接表 代码
#includecstdio
using namespace std;
struct woc{int next,x,y,w;
};
woc a[500001];//邻接表
int n,m,k,state[10001],ls[10001],t,head,tail,f[10001];
bool v[10001];
int main()
{scanf(%d%d%d,n,m,k);state[1]k;//第一个点for (int i1;im;i){scanf(%d%d%d,a[i].x,a[i].y,a[i].w);a[i].nextls[a[i].x];ls[a[i].x]i;//邻接表}for (int i1;in;i) f[i]2147483647;//初始化head0;tail1;v[state[1]]true;//标记f[k]0;while (head!tail)//注意不能是{head;//出队head(head-1)%n1;//循环队列tls[state[head]];//读取边while (t!0){if (f[a[t].x]a[t].wf[a[t].y]){f[a[t].y]f[a[t].x]a[t].w;//松弛if (!v[a[t].y]){tail;//入队tail(tail-1)%n1;//循环队列state[tail]a[t].y;v[a[t].y]true;//标记}}ta[t].next;//下一条边}v[state[head]]false;//解封}f[k]0;for (int i1;in;i)printf(%d ,f[i]);//输出
}
