成都高新区规划国土建设局网站,饮食网站开发需求,重庆餐饮品牌策划公司,阿里企业邮箱登陆题目
一个有向图#xff0c;每个点有个默认方向和若干个其他方向#xff0c;走默认方向权值为0#xff0c;其他方向权值为1#xff0c;求最短路
输入
3 2 1(3个点#xff0c;点2到点1) 2 2 3#xff08;2个点#xff0c;起点为1#xff0c;2为默认点#xff0c;3为…题目
一个有向图每个点有个默认方向和若干个其他方向走默认方向权值为0其他方向权值为1求最短路
输入
3 2 1(3个点点2到点1) 2 2 32个点起点为12为默认点3为其他点 2 3 12个点起点为23为默认点1为其他点 2 1 2
输出
0 解题思路
其实就像我题目说的那样默认方向权值为0其他方向权值为1求最短路。这里用SPFA算法。 代码
#includecstdio
using namespace std;
struct woc{int next,x,y,w;
};//日常邻接表
woc a[50001];
int xx,yy,n,m,k,state[10001],ls[10001],t,head,tail,f[10001],star,over;
bool v[10001];
int main()
{scanf(%d%d%d,n,star,over);state[1]1;int u0; for (int i1;in;i){scanf(%d,xx);for (int j1;jxx;j){scanf(%d,yy);if (j1) a[u].w0;else a[u].w1;//判断默认方向a[u].nextls[i];ls[i]u;a[u].xi;a[u].yyy;//邻接表}} for (int i1;in;i) f[i]2147483647;head0;tail1;state[1]star;v[state[1]]true;f[star]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;//解封}if (f[over]2147483647) printf(-1);//如果无解else printf(%d\n,f[over]);
}
