算出了$d[i]$偏大
by 小元勋 @ 2019-08-16 20:18:41
```
#include <bits/stdc++.h>
using namespace std;
#define maxn 110
#define maxm 5010
#define INF 2139062143
int ans=0,maxd=0,can[maxm],pre_u[maxn],pre_e[maxn],vis[maxn],d[maxn],n,m,head[maxn],size=1;
struct edge {
int v,w,nxt;
}e[maxm<<1];
struct hepnode {
int pos,dis;
bool operator < (const hepnode& rhs) const {
return dis > rhs.dis;
}
};
inline void init_() {
freopen("a.txt","r",stdin);
}
inline int read_() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}
inline void clean_() {
memset(head,-1,sizeof(head));
}
inline void add_(int u,int v,int w) {
e[++size].v=v;
e[size].w=w;
e[size].nxt=head[u];
head[u]=size;
}
inline void Dijkstra_first_(int s) {
memset(d,0x7f,sizeof(d));
memset(vis,0,sizeof(vis));
d[s]=0;
queue<hepnode>q;
q.push((hepnode) {s,d[s]} );
while(!q.empty()) {
hepnode pdc=q.front();
q.pop();
int u=pdc.pos;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];~i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w;
if(d[v]==INF||d[v]>d[u]+w) {
d[v]=d[u]+w;
pre_u[v]=u;pre_e[v]=i;
q.push((hepnode) {v,d[v]} );
}
}
}
ans=d[n];
}
inline void Dijkstra_(int s) {
memset(d,0x7f,sizeof(d));
memset(vis,0,sizeof(vis));
d[s]=0;
queue<hepnode>q;
q.push((hepnode) {s,d[s]} );
while(!q.empty()) {
hepnode pdc=q.front();
q.pop();
int u=pdc.pos;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];~i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w;
if(d[v]==INF||d[v]>d[u]+w) {
d[v]=d[u]+w;
q.push((hepnode) {v,d[v]} );
}
}
}
maxd=max(maxd,d[n]);
// printf("%d\n",maxd);
}
void readda_() {
n=read_();m=read_();
clean_();
int x,y,z;
for(int i=1;i<=m;++i) {
x=read_();y=read_();z=read_();
add_(x,y,z);add_(y,x,z);
}
Dijkstra_first_(1);
int cnt=0;
for(int i=n;i!=1;i=pre_u[i]) {
can[++cnt]=pre_e[i];
}
for(int i=1;i<=cnt;++i) {
int b=e[can[i]].w;
e[can[i]].w*=2;
e[can[i]^1].w*=2;
// printf("%d %d \n",can[i],e[can[i]].w);
Dijkstra_(1);
e[can[i]].w/=2;
e[can[i]^1].w/=2;
// printf("%d %d \n",can[i],e[can[i]].w);
}
printf("%d",maxd-ans);
}
int main() {
init_();
readda_();
return 0;
}
```
by 小元勋 @ 2019-08-16 20:18:57
但我真没查出错，我太难了
by 小元勋 @ 2019-08-16 20:19:24
太难了
by 小元勋 @ 2019-08-16 20:25:24
我太难了
by 小元勋 @ 2019-08-16 20:30:15
您太~~男♂~~强了
by oyblxzd @ 2019-08-16 20:53:50
@[何元勋](/space/show?uid=109427) 哇，神元勋！orz！
by Social_Zhao @ 2019-10-02 11:03:26