网站开发常用标签,极简wordpress,网站建设和成本,网站轮播广告代码【题目链接】:https://vjudge.net/contest/164884#problem/D 【题意】 给你一张图; 图中有些路是完好的;但有些路还没修好; 先不管路有没有修好; 问你从起点到终点的最短路; 如果最短路上有没修好的路,那么你要把它修好; 而不在最短路上的,如果是完好的路,你需要把它摧毁… 【题目链接】:https://vjudge.net/contest/164884#problem/D 【题意】 给你一张图; 图中有些路是完好的;但有些路还没修好; 先不管路有没有修好; 问你从起点到终点的最短路; 如果最短路上有没修好的路,那么你要把它修好; 而不在最短路上的,如果是完好的路,你需要把它摧毁(???) 让你选出这么一条最短路,使得受影响的路(被摧毁的和修好的路的数目总和)最少; 【题解】 受影响的路即是: 最短路上的没修好的路非最短路上的修好的路; 也即; 最短路的长度-最短路上的修好的路整张图上修好的路-最短路上修好的路 也即 最短路的长度整张图上修好的路-2*最短路上修好的路; 要让受影响的路最少; 即让最短路上修好的路最大就好; 这个可以在做spfa的时候顺便得到; 即最短路相同,再判断一下修好的路的个数; 按照那个公式算出受影响的路; 然后记录每个点的前缀; 最短路上没修好的路把它修好(输出); 不是最短路上的修好的路把它破坏(输出); 【Number Of WA】 0 【完整代码】 #include bits/stdc.h
using namespace std;
#define lson l,m,rt1
#define rson m1,r,rt1|1
#define LL long long
#define rep1(i,a,b) for (int i a;i b;i)
#define rep2(i,a,b) for (int i a;i b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen(F:\\rush.txt,r,stdin)
#define Close() ios::sync_with_stdio(0),cin.tie(0)typedef pairint,int pii;
typedef pairLL,LL pll;const int dx[9] {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] {0,0,0,-1,1,-1,1,-1,1};
const double pi acos(-1.0);const int N 1e550;
const int INF 0x3f3f3f3f;struct abc{int x,y,z;
};int n,m,all1,k;
abc a[N];
vector pii G[N];
pii dis[N],pre[N];
queue int dl;
bool inq[N],bo[N];void spfa()
{rep1(i,1,n)dis[i] mp(INF,0);dis[1].fi 0;dl.push(1);inq[1] true;while (!dl.empty()){int x dl.front();dl.pop();inq[x] false;for (pii temp:G[x]){int y temp.fi,w a[temp.se].z;if (dis[y].fidis[x].fi1 || (dis[y].fidis[x].fi1 dis[y].sedis[x].sew)){dis[y].fi dis[x].fi1;dis[y].se dis[x].sew;pre[y] mp(x,temp.se);if (!inq[y]){inq[y] true;dl.push(y);}}}}
}int main()
{//Open();cin n m;rep1(i,1,m){cin a[i].x a[i].y a[i].z;G[a[i].x].pb(mp(a[i].y,i));G[a[i].y].pb(mp(a[i].x,i));all1a[i].z;}spfa();k dis[n].fiall1-2*dis[n].se;cout k endl;int now n;while (now!1){int temp pre[now].se;if (a[temp].z0)cout a[temp].x a[temp].y 1endl;bo[temp] 1;now pre[now].fi;}rep1(i,1,m)if (!bo[i] a[i].z1)cout a[i].x a[i].y 0endl;return 0;
}转载于:https://www.cnblogs.com/AWCXV/p/7626299.html
