山东省住房与城乡建设厅网站,河东苏州网站建设,网站制作开发公司,石家庄机票网站建设P4568 [JLOI2011]飞行路线
题意#xff1a;
n个城市#xff0c;m个航班#xff0c;你有k次免费坐航班的机会#xff0c;问从s到t最少花费是多少#xff1f;
题解#xff1a;
分层图问题 简单说说什么是分层图#xff1a; 其实就是将一个平面的图重新建图#xff0c…P4568 [JLOI2011]飞行路线
题意
n个城市m个航班你有k次免费坐航班的机会问从s到t最少花费是多少
题解
分层图问题 简单说说什么是分层图 其实就是将一个平面的图重新建图有好几层 具体的说每层图之间各自连边与原图一样但是相邻的两层图之间根据原来的关系进行连边 虽然是多层图但是用一维的关系就可以 比如 当有3个点3层图时 1对应的就是 1n 和 12 * n 2对应的就是 2n 和 22 * n … 当存在n个点k层图时 1对应的就是1n * 0, 1 n* 1…1n * (k-1) 而且每一层的图都遵循只能从上面的图到下一层图不能反过来 那建这么多层图的目的是什么呢 你可以理解成是一种尝试就比如本题我们向下一层就代表拥有一次免费乘坐的机会如果我们有k次免费乘坐机会就建k层图(最原本的是第0层)。 每层图内部是原本的边权关系而图与图之间是0边权(就相当于是免费乘坐机会)
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime clock(); //计时开始freopen(in.txt,r,stdin);#endif
}
void Time_test(){#ifdef ONLINE_JUDGE#elseendTime clock(); //计时结束printf(\n运行时间为:%lfs\n,(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif
}
const int maxn3e59;
struct node{int w,now;inline bool operator(const node x)const{return wx.w;}
};
priority_queuenodeq;
int dis[maxn],vis[maxn];
vectorPIIvec[maxn];
int s,t;int n,m,k;
void dijkstra(){memset(dis,INF_int,sizeof(dis));dis[s]0;q.push((node){0,s});while(!q.empty()){node xq.top();q.pop();int ux.now;if(vis[u])continue;vis[u]1;for(auto it:vec[u]){int vit.first;int wit.second;if(dis[v]dis[u]w){dis[v]dis[u]w;q.push({dis[v],v});}}}
}int main()
{//rd_test();cinnmk;cinst;for(int i1;im;i){int u,v,w;cinuvw;vec[u].push_back({v,w});vec[v].push_back({u,w});for(int j1;jk;j){//每一层vec[uj*n].push_back({vj*n,w});vec[vj*n].push_back({uj*n,w});//层与层之间 vec[u(j-1)*n].push_back({vj*n,0});vec[v(j-1)*n].push_back({uj*n,0});}}dijkstra();int minnINF_int;for(int i0;ik;i){minnmin(minn,dis[ti*n]);}coutminn;return 0;//Time_test();
}
