@[yangyuecong](/user/487959) 边可能重复，你没有判重
by EastPorridge @ 2023-01-06 17:17:23
@[EastPorridge](/user/230865) 谢谢（已关注）
by yyc_qwq @ 2023-01-06 17:18:49
@[EastPorridge](/user/230865) 怎么改？（我很垃）
by yyc_qwq @ 2023-01-06 17:21:43
@[yangyuecong](/user/487959) 写个 map 存下来，读完之后离线加边就可以了；；；
by EastPorridge @ 2023-01-06 17:23:37
@[EastPorridge](/user/230865) 好的
by yyc_qwq @ 2023-01-06 17:27:04
@[EastPorridge](/user/230865) 现在77了（2WA,1RE）
```cpp
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
const long long N=114514;
const long long inf=0x3f3f3f3f;
struct edge
{
long long v, w;
};
struct node {
long long dis, u;
bool operator<(const node& a) const { return dis > a.dis; }
};
vector<edge> e[N];
long long dis[N], vis[N],cnt[N];
priority_queue<node> q;
map<node,int> mp[2000];
void dijkstra(long long n, long long s){
memset(dis, 63, sizeof(dis));
dis[s] = 0;
q.push({0, s});
while (!q.empty()){
long long u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed : e[u]){
long long v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
cnt[v] = cnt[u];
q.push({dis[v], v});
}else if (dis[v] == dis[u] + w){
cnt[v] = cnt[v]+cnt[u];
}
}
}
}
int main(){
long long n,m;
cin >> n >> m;
for (long long i = 1; i <= m; i++){
long long u,v,w;
cin >> u >> v >> w;
if(mp[u][{v,w}]==0) {
e[u].push_back({v, w});
mp[u][{v,w}]=1;
}
}
cnt[1] = 1;
dijkstra(n,1);
if(dis[n]==inf){
cout << "No answer" << endl;
}else{
cout << dis[n] << ' ' << cnt[n] << endl;
}
return 0;
}
by yyc_qwq @ 2023-01-06 17:36:41
@[yangyuecong](/user/487959) 稍等，我给你调一下吧
by EastPorridge @ 2023-01-06 17:38:59
@[EastPorridge](/user/230865) 好心大佬，受我一跪
by yyc_qwq @ 2023-01-06 17:40:49
@[yangyuecong](/user/487959)
```cpp
/*
text
*/
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
inline int read()
{
int x=0; char c=getchar(); bool f=0;
for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x=f ? -x : x;
}
using namespace std;
const long long N=114514;
const long long inf=0x3f3f3f3f;
struct edge
{
long long v, w;
};
struct node {
long long dis, u;
bool operator<(const node& a) const { return dis > a.dis; }
};
vector<edge> e[N];
long long dis[N], vis[N],cnt[N];
priority_queue<node> q;
map<pair<int,int>,int> mp;
void dijkstra(long long s){
memset(dis, 63, sizeof(dis));
dis[s] = 0;
q.push({0, s});
while (!q.empty()){
long long u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed : e[u]){
long long v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
cnt[v] = cnt[u];
q.push({dis[v], v});
}else if (dis[v] == dis[u] + w){
cnt[v] = cnt[v]+cnt[u];
}
}
}
}
int main()
{
int n=read(),m=read();
if(m == 0) return puts("No answer"),0;
for (long long i = 1; i <= m; i++)
{
int u=read(),v=read(),w=read();
auto t=make_pair(u,v);
if(! mp[t]) mp[t]=w; else mp[t]=min(mp[t],w);
}
for(auto it : mp) e[it.first.first].emplace_back(edge{it.first.second,it.second});
cnt[1] = 1; dijkstra(1);
if(dis[n]==inf){
cout << "No answer" << endl;
}else{
cout << dis[n] << ' ' << cnt[n] << endl;
}
return 0;
}
```
by EastPorridge @ 2023-01-06 17:50:49
@[yangyuecong](/user/487959) 你的判法有问题，然后 cin T 了，给你加了个快读才过。
by EastPorridge @ 2023-01-06 17:51:56