Submission #3006348
Source Code Expand
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <math.h> #define MOD 1000000007 #define INFTY (1<<20) typedef long long ll; using namespace std; int n,m,t; int A[100001]; vector<pair<int,int>> v[100001]; vector<pair<int,int>> g[100001]; ll d1[100001]; ll d2[100001]; void dijkstra1(){ priority_queue<pair<int,int>> PQ; //int d[n]; for(int i=0;i<n;i++) d1[i]=INFTY; d1[0]=0; PQ.push(make_pair(0,0)); while(!PQ.empty()){ pair<int,int> f=PQ.top(); PQ.pop(); int u=f.second; if(d1[u]<f.first*(-1)) continue; for(int j=0;j<v[u].size();j++){ int x=v[u][j].first; if(d1[x]>d1[u]+v[u][j].second){ d1[x]=d1[u]+v[u][j].second; PQ.push(make_pair(d1[x]*(-1),x)); } } } //ll ans=0; /*for(int i=0;i<n;i++){ if(d[i]*2>=t) continue; ans=max(ans,((ll)t-d[i]*2)*A[i]); //cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl; } cout<<ans<<endl;*/ } void dijkstra2(){ priority_queue<pair<int,int>> PQ; //int d[n]; for(int i=0;i<n;i++) d2[i]=INFTY; d2[0]=0; PQ.push(make_pair(0,0)); while(!PQ.empty()){ pair<int,int> f=PQ.top(); PQ.pop(); int u=f.second; if(d2[u]<f.first*(-1)) continue; for(int j=0;j<g[u].size();j++){ int x=g[u][j].first; if(d2[x]>d2[u]+g[u][j].second){ d2[x]=d2[u]+g[u][j].second; PQ.push(make_pair(d2[x]*(-1),x)); } } } ll ans=0; for(int i=0;i<n;i++){ if(d1[i]+d2[i]>=t) continue; ans=max(ans,(t-d1[i]-d2[i])*A[i]); //cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl; } cout<<ans<<endl; } int main(){ //int n,m,t; cin>>n>>m>>t; //ll A[n]={}; for(int i=0;i<n;i++) cin>>A[i]; //vector<pair<int,int>> v[n]; for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; a--; b--; v[a].push_back(make_pair(b,c)); g[b].push_back(make_pair(a,c)); } dijkstra1(); dijkstra2(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - トレジャーハント |
User | snow39 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2042 Byte |
Status | WA |
Exec Time | 123 ms |
Memory | 13184 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 50 | 0 / 50 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 3 ms | 4992 KB |
00_example_02.txt | AC | 3 ms | 4992 KB |
00_example_03.txt | AC | 3 ms | 4992 KB |
10_rand_01.txt | AC | 8 ms | 5376 KB |
10_rand_02.txt | AC | 29 ms | 6272 KB |
10_rand_03.txt | AC | 11 ms | 5504 KB |
10_rand_04.txt | AC | 5 ms | 5120 KB |
10_rand_05.txt | WA | 12 ms | 5632 KB |
10_rand_06.txt | WA | 11 ms | 5760 KB |
10_rand_07.txt | WA | 16 ms | 6144 KB |
10_rand_08.txt | AC | 8 ms | 5376 KB |
10_rand_09.txt | AC | 14 ms | 5888 KB |
10_rand_10.txt | AC | 5 ms | 5120 KB |
10_rand_12.txt | AC | 50 ms | 6784 KB |
10_rand_13.txt | AC | 46 ms | 6656 KB |
30_max_01.txt | AC | 103 ms | 8564 KB |
30_max_02.txt | AC | 117 ms | 9360 KB |
30_max_03.txt | AC | 86 ms | 8100 KB |
30_max_04.txt | AC | 119 ms | 11136 KB |
30_max_05.txt | AC | 123 ms | 11136 KB |
30_max_06.txt | AC | 122 ms | 11136 KB |
40_corner_01.txt | AC | 105 ms | 13184 KB |
40_corner_02.txt | WA | 106 ms | 13184 KB |
40_corner_03.txt | WA | 109 ms | 13184 KB |
40_corner_04.txt | WA | 113 ms | 13184 KB |
50_small_01.txt | AC | 4 ms | 4992 KB |
50_small_02.txt | AC | 3 ms | 4992 KB |
50_small_03.txt | AC | 3 ms | 4992 KB |
50_small_04.txt | AC | 3 ms | 4992 KB |
50_small_05.txt | AC | 5 ms | 4992 KB |
50_small_06.txt | AC | 4 ms | 4992 KB |
50_small_07.txt | AC | 3 ms | 4992 KB |
50_small_08.txt | AC | 2 ms | 4992 KB |
50_small_09.txt | AC | 3 ms | 4992 KB |
50_small_10.txt | AC | 3 ms | 4992 KB |
60_hand_01.txt | WA | 2 ms | 4992 KB |
60_hand_02.txt | AC | 3 ms | 4992 KB |
60_hand_03.txt | AC | 3 ms | 4992 KB |
60_hand_04.txt | AC | 2 ms | 4992 KB |
70_max_01.txt | AC | 28 ms | 5888 KB |
70_max_02.txt | AC | 28 ms | 5888 KB |
70_max_03.txt | AC | 28 ms | 5888 KB |