微信h5商城网站,wordpress安装网页太简单了,家装公司利润一般多少,管网建设题意#xff1a;有向图有N个点#xff0c;当电车进入交叉口#xff08;某点#xff09;时#xff0c;它只能在开关指向的方向离开。 如果驾驶员想要采取其他方式#xff0c;他/她必须手动更换开关。当驾驶员从路口A驶向路口B时#xff0c;他/她尝试选择将他/她不得不手动…题意有向图有N个点当电车进入交叉口某点时它只能在开关指向的方向离开。 如果驾驶员想要采取其他方式他/她必须手动更换开关。当驾驶员从路口A驶向路口B时他/她尝试选择将他/她不得不手动更换开关的次数最小化的路线。 编写一个程序该程序将计算从交点A到交点B所需的最小开关更改次数。第i个交点处的开关最初指向列出的第一个交点的方向。 分析对于某点i去往其直接可到达的点列表中的第一个点时不需要更换开关等价于边长为0而其他的点需要更换开关等价于边长为1。dijkstra裸题。 #includecstdio
#includemap
#includeiostream
#includecstring
#includequeue
using namespace std;
const int MAXN 100 10;
const int INF 0x3f3f3f3f;
struct Edge{int from, to, dist;Edge(int f, int t, int d):from(f), to(t), dist(d){}
};
struct HeapNode{int d, u;HeapNode(int dd, int uu):d(dd), u(uu){}bool operator (const HeapNoderhs)const{return d rhs.d;}
};
struct Dijkstra{int n, m;vectorint G[MAXN];vectorEdge edges;bool done[MAXN];int d[MAXN];int p[MAXN];void init(int n){this - n n;for(int i 1; i n; i) G[i].clear();edges.clear();}void AddEdge(int from, int to, int dist){edges.push_back(Edge(from, to, dist));m edges.size();G[from].push_back(m - 1);}void dijkstra(int s){priority_queueHeapNode q;for(int i 1; i n; i) d[i] INF;memset(done, false, sizeof done);d[s] 0;q.push(HeapNode(0, s));while(!q.empty()){HeapNode top q.top();q.pop();if(done[top.u]) continue;done[top.u] true;int len G[top.u].size();for(int i 0; i len; i){Edge e edges[G[top.u][i]];if(d[top.u] e.dist d[e.to]){d[e.to] d[top.u] e.dist;p[e.to] G[top.u][i];q.push(HeapNode(d[e.to], e.to));}}}}
}dij;
int main(){int N, A, B;scanf(%d%d%d, N, A, B);dij.init(N);for(int i 1; i N; i){int k, x;scanf(%d, k);for(int j 0; j k; j){scanf(%d, x);if(j 0) dij.AddEdge(i, x, 0);else dij.AddEdge(i, x, 1);}}dij.dijkstra(A);if(dij.d[B] INF) printf(-1\n);else printf(%d\n, dij.d[B]);return 0;
}转载于:https://www.cnblogs.com/tyty-Somnuspoppy/p/9084352.html
