思路：
判负环（最短路问题若成环一定是负环）。问题：没有保证环必须经过点1啊，我认为应该是遍历全部的联通块，最后判断有没有负环，怎么大家全都直接从1开始判负环了。我也还不会写，只好也打一个Bellman-Ford。500点，2500边，稠密图，用邻接表反而超时。
代码：
1235ms 1644kB
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
= 505;
int mp
[maxn
][maxn
];
int N
,M
,W
;
struct NODE
{
int id
,dis
;
NODE(int id
,int dis
) : id(id
) , dis(dis
) {} ;
};
int dis
[maxn
];
bool
BELL(){
memset(dis
,INF
,sizeof(dis
));
dis
[1] = 0;
int t
;
for(t
=1;t
<N
;t
++){
bool flag
= false
;
for(int u
=1;u
<=N
;u
++)
for(int v
=1;v
<=N
;v
++)
if(dis
[v
] > dis
[u
] + mp
[u
][v
]){
dis
[v
] = dis
[u
] + mp
[u
][v
];
flag
= true
;
}
if(!flag
)
break;
}
if(t
== N
)
return true
;
return false
;
}
int main(){
int T
;cin
>>T
;
while(T
--){
cin
>>N
>>M
>>W
;
memset(mp
,INF
,sizeof(mp
));
for(int i
=1;i
<maxn
;i
++)
mp
[i
][i
] = 0;
for(int i
=1;i
<=M
;i
++){
int u
,v
,t
;
cin
>>u
>>v
>>t
;
mp
[u
][v
] = min(mp
[u
][v
] , t
);
mp
[v
][u
] = min(mp
[v
][u
] , t
);
}
for(int i
=1;i
<=W
;i
++){
int u
,v
,t
;
cin
>>u
>>v
>>t
;
mp
[u
][v
] = min(mp
[u
][v
] , -t
);
mp
[u
][v
] = min(mp
[v
][u
] , -t
);
}
if(BELL())
cout
<<"YES"<<endl
;
else
cout
<<"NO"<<endl
;
}
return 0;
}
邻接矩阵：TLE
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
= 505;
int N
,M
,W
;
int tail
[maxn
];
struct EDGE
{
int to
;
int w
;
int fo
;
};
EDGE E
[maxn
*5];int cnt
;
int dis
[maxn
];
void INIT(){
cnt
=0;
memset(tail
,-1,sizeof(tail
));
memset(dis
,INF
,sizeof(dis
));
return ;
}
void AddEdge(int u
,int v
,int w
){
cnt
++;
E
[cnt
].w
= w
;
E
[cnt
].to
= v
;
E
[cnt
].fo
= tail
[u
];
tail
[u
] = cnt
;
}
bool
BELL(){
dis
[1] = 0;
int t
;
for(t
=1;t
<N
;t
++){
bool flag
= false
;
for(int i
=1;i
<=N
;i
++){
for(int j
=tail
[i
];~j
;j
=E
[j
].fo
){
if(dis
[E
[j
].to
] > dis
[i
] + E
[j
].w
){
dis
[E
[j
].to
] = dis
[i
] + E
[j
].w
;
flag
= true
;
}
}
}
if(!flag
)
break;
}
return t
== N
? true
: false
;
}
int main(){
int T
;cin
>>T
;
while(T
--){
INIT();
cin
>>N
>>M
>>W
;
int u
,v
,w
;
for(int i
=1;i
<=M
;i
++){
cin
>>u
>>v
>>w
;
AddEdge(u
,v
,w
);
AddEdge(v
,u
,w
);
}
for(int i
=1;i
<=W
;i
++){
cin
>>u
>>v
>>w
;
AddEdge(u
,v
,-w
);
}
if(BELL())
cout
<<"YES"<<endl
;
else
cout
<<"NO"<<endl
;
}
return 0;
}
