为女足世界杯创建一个网站,wordpress 插件 封面,3d网站怎么做,英才网传送门 题意#xff1a; 给一个图#xff0c;111号点为中心点#xff0c;定义dis[i]dis[i]dis[i]表示111号点到iii的距离。现在有三种移动方式 (1)(1)(1)从iii移动到jjj且dis[i]dis[j]dis[i]dis[j]dis[i]dis[j]。 (2)(2)(2)从iii移动到jjj且dis[i]dis[j]dis…传送门 题意 给一个图111号点为中心点定义dis[i]dis[i]dis[i]表示111号点到iii的距离。现在有三种移动方式 (1)(1)(1)从iii移动到jjj且dis[i]dis[j]dis[i]dis[j]dis[i]dis[j]。 (2)(2)(2)从iii移动到jjj且dis[i]dis[j]dis[i]dis[j]dis[i]dis[j]。 (3)(3)(3)结束旅程。 其中第二种移动方式最多只能使用一次。问每个点能到达的离起点最近的点的距离是多少。
思路 我们维护一个dpdpdp数组dp[i]dp[i]dp[i]表示iii点能到达的距离起点最近的距离。转移方程也比较好想啦 {dp[i]min(dp[i],dp[j]),dis[i]dis[j]dp[i]min(dp[i],dis[j]),dis[i]dis[j]\begin{cases} dp[i]min(dp[i],dp[j]),dis[i]dis[j] \\ dp[i]min(dp[i],dis[j]),dis[i]dis[j] \end{cases}{dp[i]min(dp[i],dp[j]),dis[i]dis[j]dp[i]min(dp[i],dis[j]),dis[i]dis[j] dp[i]dp[i]dp[i]的初始值为dis[i]dis[i]dis[i]转移的时候只需要按照disdisdis从大到小转移即可。按照深度排个序就好了不知道为什么我写了个优先队列
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int dis[N],p[N];
int f[N],g[N];
vectorintv[N];
bool st[N];struct cmp
{bool operator () (int a,int b){return dis[a]dis[b];}
};int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--){scanf(%d%d,n,m);for(int i1;in;i) v[i].clear(),st[i]false,p[i]i,dis[i]INF;for(int i1;im;i){int a,b; scanf(%d%d,a,b);v[a].pb(b);}dis[1]0; st[1]true;queueintqq; qq.push(1);while(qq.size()){int tqq.front(); qq.pop();for(auto x:v[t]) if(!st[x]) dis[x]dis[t]1,qq.push(x),st[x]true;}priority_queueint,vectorint,cmpq;int mx0;for(int i1;in;i) st[i]false,f[i]dis[i];for(int i1;in;i) q.push(i),st[i]true;while(q.size()){int uq.top(); q.pop();for(auto x:v[u]){if(dis[x]dis[u]) f[u]min(f[u],f[x]);else f[u]min(f[u],dis[x]);if(!st[u]) q.push(u),st[u]true;}}for(int i1;in;i) printf(%d ,f[i]);}return 0;
}
/**/
