德令哈网站建设公司,wordpress内置采集插件,网页版传奇下载,网络推广专员是干什么的题干#xff1a;
由于临近广西大学建校90周年校庆#xff0c;西大开始了喜闻乐见的校园修缮工程#xff01;
然后问题出现了#xff0c;西大内部有许许多多的道路#xff0c;据统计有N栋楼和M条道路#xff08;单向#xff09;#xff0c;每条路都有“不整洁度”W
由于临近广西大学建校90周年校庆西大开始了喜闻乐见的校园修缮工程
然后问题出现了西大内部有许许多多的道路据统计有N栋楼和M条道路单向每条路都有“不整洁度”W现在校方想知道从S楼到T楼的所有路径中“不整洁度”乘积最小是多少。
由于答案可能很大所以你需要将最后的答案对1097取模。
输入描述: 第一行为四个整数N、M、S、T意义如上。
第2至第M1行每行表示一条道路有三个整数分别表示每条道路的起点u终点v和“不整洁度”W。
输入保证没有自环可能有重边。 其中W一定是2的整数次幂。
输出描述: 输出一个整数表示最小的不整洁度之乘积对1097取模的结果。
若无解请输出 -1 示例1
输入
复制
4 4 1 3
1 2 8
1 3 65536
2 4 2
4 3 16
输出
复制
256
解题报告 把乘法转化成加法就可以跑Dijkstra了。。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
struct Edge {int to;int ne;ll w;
} e[MAX];
struct Point {int o;ll c;Point(){}Point(int o,ll c):o(o),c(c){}friend bool operator (const Point a,const Point b) {return a.c b.c;}
};
const ll INF 0x3f3f3f3f3f3f;
const ll mod 1e9 7;
int n,m,s,t;
int tot;
int head[MAX];
ll dis[MAX];
bool vis[MAX];
void add(int x,int y,ll w) {e[tot].to y;e[tot].w w;e[tot].ne head[x];head[x] tot;
}
ll qpow(ll a,ll k) {ll res 1;while(k) {if(k1) res (res * a) % mod;k1;a (a*a)%mod;}return res % mod;
}
void Dijkstra() {for(int i 1; in; i) dis[i] INF;memset(vis,0,sizeof vis);dis[s] 0;priority_queuePoint pq;pq.push(Point(s,0));while(!pq.empty()) {Point cur pq.top();pq.pop(); if(vis[cur.o]) continue;vis[cur.o]1;for(int i head[cur.o]; i!-1; ie[i].ne) {//if(vis[cur.o]) continue;if(e[i].w dis[cur.o] dis[e[i].to]) {dis[e[i].to] e[i].w dis[cur.o];pq.push(Point(e[i].to,dis[e[i].to]));}}}}int main()
{ll c;memset(head,-1,sizeof head);cinnmst;for(int i 1,a,b; im; i) {scanf(%d%d%lld,a,b,c);ll tmp (ll)log2(c);add(a,b,tmp);}Dijkstra();if(dis[t] INF) puts(-1);else printf(%lld\n,qpow(2,dis[t]%mod));return 0 ;}
